Estimating Node Similarity by Sampling Streaming Bipartite Graphs
Nesreen K. Ahmed∗

Nick Duffield†

arXiv:1712.08685v1 [cs.SI] 22 Dec 2017

Abstract
Bipartite graph data increasingly occurs as a stream of
edges that represent transactions, e.g., purchases by retail customers. Applications such as recommender systems employ neighborhood-based measures of node similarity, such as the pairwise number of common neighbors (CN) and related metrics. While the number of
node pairs that share neighbors is potentially enormous,
in real-word graphs only a relatively small proportion
of all pairs have a large number of common neighbors.
This motivates finding a weighted sampling approach
that preferentially samples such node pairs.
This paper presents a new sampling algorithm that
provides a fixed size unbiased estimate of the similarity
(or projected) graph on a bipartite edge stream. The
algorithm has two components. First, it maintains
a reservoir of sampled bipartite edges with sampling
weights that favor selection of high similarity nodes.
Second, arriving edges generate a stream of similarity
updates based on their adjacency with the current
sample. These updates are aggregated in a second
reservoir sample-based stream aggregator to yield the
final unbiased estimate. Experiments on real world
graphs show that a 10% sample ar each stages yields
estimates of high similarity edges with weighted relative
errors of about 10−2 .
1

Introduction

Collaborative Filtering and Similarity Measures.
The analysis of massive bipartite graphs has become
important in many applications of data mining, e.g.,
in business, science, and engineering. Bipartite graphs
represent the relationships between two types of node,
e.g., between business customers and the products or
services that they consume [1] or between individuals
and the diseases that they are subject to [2].
Many applications of bipartite graphs focus on
determining the similarity between node pairs. In
Collaborative Filtering, recommendations for customer
purchases are predicted from the purchase histories of
∗ Intel

Labs, Email: nesreen.k.ahmed@intel.com
† Texas A&M University, Email: duffieldng@tamu.edu
‡ Texas A&M University, Email: xialiangzhen123@tamu.edu

Liangzhen Xia

‡

similar customers. These predictions are ranked by
scores that express the similarity between customers,
and the resulting recommendations are prioritized by
score rank order. Node similarities have been used
for link prediction in general graphs [3], and various
scorings have been applied to collaborative filtering in
bipartite graphs. Three classes are distinguished: (i)
neighborhood based scores based in overlap of neighbor
sets [4]; (ii) path based approaches; and (iii) random
walk methods [5] inspired by the well-known PageRank
algorithm [6]. Similarity measures are also used in link
prediction for bipartite graphs [7, 8, 9].
Graph Stream Mining: Benefits & Challenges.
Graph analytics increasingly focuses on streaming graph
data in which graph relationships are represented implicitly in a transactional stream of edges rather than
a graph database [10]. Examples include transactional
data from customer purchases in online retailers [1], and
streams of status reports from customer interfaces of
utility service providers [11]. Computing neighborhoodbased similarity is challenging in stream-graph mining
because the number of similarity relations amongst a
partition with n nodes is potentially O(n2 ). Although
filtering low degree nodes can reduce complexity by excluding some nodes from consideration, this cannot be
applied directly in the streaming case, since node degrees are not fully known while the stream is in progress.
The Similarity Graph and Its Sampling Properties. We argue that the observed properties of neighborhood based similarity scores in real-world graph data
provide an opportunity for space and computational
savings by sampling, while providing score estimates
that are sufficiently accurate for many applications. We
focus on the Common Neighbors (CN) score, defined for
two nodes x, y as the size C(x, y) = |N (x) ∩ N (y)| of
the intersection of their neighbor sets N (x) and N (y).
Equivalently, C(x, y) is the number of wedges (x, z, y)
connecting x and y. CN is a component of other scores
for recommendation and link prediction [12], including
the Jaccard Similarity
J(x, y) =

C(x, y)
|N (x) ∩ N (y|
=
|N (x) ∪ N (y)|
|N (x)|+|N (y)|−C(x, y)

Since estimating node degree is a relatively easy prob-

Figure 1: Edge Similarity (left) and Cumulative Fraction (right) as function of dense edge rank for Movie
dataset
lem, estimating J essentially reduces to estimating C.
The similarity or projected graph connects node
pairs x, y with non-zero weights C(x, y) that we will
call similarities. For one dataset in our study (Movie;
see Section 3.1) the similarity graph of the source component has 1.2M edges whose similarities take 6,979 distinct values that accumulate the counts of 171M wedges.
This motivates a sampling scheme that estimates similarities using a reduced set of wedge counts from small
set of relevant bipartite edges.
Figure 1 plots the similarities of Movie (left) and
their cumulative distribution (right) as a function of
their dense rank. (In dense ranking, equal size objects
receive the same rank, and ranks are consecutive).
Observe from the right plot that a small proportion of
similarity edges account for most of the low ranks, e.g.,
the first 6,000 dense ranks contain only about 1% of
the total edges. From the left plot, the remaining 99%
high rank edges have relatively low edge similarities, 100
or less, compared with a maximum similarity of about
3 × 104 . Thus the higher similarity edges constitute
a relatively small fraction of all edges. A weighted
sampling scheme that preferentially selects bipartite
edges with high node degree from the edge stream, will
also favor node pairs with high similarity.

updates, which is also weighted to favor larger aggregates, i.e., the similarity estimates.
Section 2 presents our new algorithm for weighted
graph stream sampling in a fixed size reservoir, in which
bipartite edge weights can adapt to their topological importance. Unbiasedness is established for edge count
estimators that are used for similarity estimation, and
the computational properties analyzed. In Section 3 we
evaluate algorithm accuracy using edges streams generate from three bipartite graph datasets, and introduce
some additional measures for controlling estimation error. With 10% sampling rate for both bipartite and
similarity edges, the similarities of edges with the top100 dense ranks are estimated with weighted relative
error of around 10%, and correlation between true and
estimated ranks is over 90%. A performance comparison with recent related work [13] confirms the benefits of
using a single edge reservoir that devotes storage to estimating high similarity nodes that occur in sparse networks. Moreover, in distinction with [13], our method
allows setting of a fixed size sample without any prior
knowledge of the graph represented in the stream, while
at the same sample time exploiting all reserved storage.
We review related work in Section 4 and conclude in
Section 5.
2

Similarity Estimation & Edge Sampling

2.1 Streaming Bipartite and Similarity Graphs.
Let G = (U, V, K) denote a bipartite graph with disjoint
node sets U and V and edge set K ⊂ U × V . For
e ∈ K we denote with end points u(e) ∈ U and
v(e) ∈ V . For a subset S ⊂ K of edges we denote by
U (S) = {u(e) : e ∈ S} and V (S) = {v(e) : e ∈ S} the
corresponding sets of endpoints in U and V . N (u) =
{v : (u, v) ∈ K} will denote the neighbor set of u in V
with N (U 0 ) = ∪u∈U 0 N (u) for U 0 ⊂ U . d(w) will denote
the degree of any node w ∈ U ∪ V .
The similarity graph or projected graph GU
induced by G = (U, V, K) on U , is the weighted graph
GU = (U, KU , C) where KU ⊂ U ×U and the similarity
a : F → R where C(u, u0 ) = |N (u) ∩ N (u0 )| is the
cardinality of the set of common neighbors of u and u0
and KU = {(u, u0 ) : C(u, u0 ) > 0} is the similarity edge
set. The similarity graph GV induced on V by G is
defined likewise. In the streaming bipartite graph
model, the edges K arrive in a sequence {ei : i ∈ [|K|]}
in some specified order. Kn = {ei : i ∈ [n]} will
denote the first n arriving edges and Gn = (Un , Vn , Kn )
the induced subgraph of G, where Un = U (Kn ) and
Vn = V (Kn ), and Cn the corresponding similarity.

Contribution and Outline This paper proposes a
new one pass scheme for sampling the streaming bipartite graph in fixed storage that provides unbiased
estimates of the CN similarities. Our algorithm comprises two stages. First, we construct a stream reservoir bipartite edge sample with weights chosen to minimize estimation variance for (certain sums of) similarities. Concurrently, each arriving edge generates a set
of approximate updates to the similarities, one for each
wedge formed with the bipartite graph sample. The
second stage computes an approximate summary of the 2.2 Problem Description and Approach. In this
similarity graph by sampled-based aggregation of the paper we address the following problem.

Similarity Graph Estimation from Bipartite Edge Streams: For each n, compute
bn of the
in fixed storage an unbiased estimate C
similarity Cn of the subgraph of Gn formed
from its first n edges.
Our approach has three elements. First, we maintain a weighted edge sample from the streaming bipartite graph. Second, incoming bipartite edges generate
unbiased estimators of updates to the similarity graph.
Third, a further sample based aggregation accumulates
estimators of the similarity graph in fixed storage.
2.3 Adaptive Graph Priority Sampling. We construct a weighted reservoir sample of bipartite edges in
which edge weights dynamically adapt to their topological importance. Our scheme extends Graph Priority Sampling (GPS) [14] which optimizes sampling of a
edge stream so as to estimate the cardinalities of target
sets of subgraphs, but using edge weights that are fixed
on arrival. For a reservoir of size m, we admit the first
m edges, while for t > m, the sample set comprises a
b t ≤ Kt of the first t arriving edges, with fixed
subset K
b
size |Kt |= m for each t ≥ m. This is achieved by provisionally admitting the arrival at each t > m to the
reservoir, then discarding one of the resulting m + 1
edges by the random mechanism that we now describe.
Since edges are assumed unique, each edge ei is
identified with its the arrival order i ∈ [|E|]. All sampling outcomes are determined by independent random
variables β1 , uniformly distributed in (0, 1], assigned to
each edge i on arrival. Any edge present in the sample at
time t ≥ i possess a weight wi,t whose form is described
in Section 2.4. The priority of i at time t is defined as
ri,t = wi,t /βi . Edge i is provisionally admitted to the
b0 = K
b i−1 ∪ {i}, from which
reservoir forming the set K
i
we then discard the edge of minimal priority.
This procedure leads to unbiased estimation of edge
counts in the following sense. The edge indicator
Si,t that takes the value 1 if t ≥ i and 0 otherwise,
indicates whether each i has arrived by time t. We
will construct unbiased edge estimators Sbi,t which are
nonnegative random variables that E[Sbi,t ] = Si,t , where
the expectation is over all sampling outcomes of the edge
stream in the sampling process defined below.
Define zt = mini∈Kb 0 ri,t , and set the Zi,t =
t
{zi , . . . , zt }. Let qi,t = min{1, mini≤s≤t wi,s /zs } and
pi,t = min{1, mini≤s≤t wi,s /zs∗ } where zt∗ = max Zm,t .

b 0 for all s ∈ [i, t]. In other words
any K
S
b t } = ∩s∈[i,t] {
{i ∈ K

wi,s
wi,s
> zi,s } = {βi < min
}
βi
s∈[i,t] zi,s

b t |Zi,t ] = q̃i,t := min{1, mins∈[i,t] wi,s /zi,s }.
Thus P[i ∈ K
b t since then zi,s = zs
Note that q̃i,t = qi,t when i ∈ K
for all s ∈ [i, t]. Hence when t ≥ i
(2.1)

b t )|Zi,t ]/q̃i,t = 1 = Si,t
E[Sbi,t |Zi,t ] = P[I(i ∈ K

independent of Zi,t and hence E[Sbi,t ] = Si,t . Trivially
Sbi,t = 0 = Si,t for t < i. The proof complete provided
we can show that i ∈ Kt implies pi,t = qi,t .
Let dt denote the edge discarded during processing
b i and since
arrival t. By assumption, i is admitted to K
wj,t is non-decreasing in t, zi = zi,i = wdi ,i /βdi ≥
wdi ,s /βdi > zs for all s ∈ [di , i] in order that di ∈ Ks
for all s ∈ [di , i − 1]. Iterating the argument we obtain
that zi ≥ Zm,i and hence zi = zi∗ and pi,i = qi,i . The
argument is completed by induction. Assume pi,s = qi,s
∗
= zt+1
for s > i. If in addition zt+1 > zt∗ , then zt+1
∗
∗
and hence pi,s+1 = qi,s+1 . If zs+1 ≤ zs then zs = zs+1
∗
∗
and hence wi,s+1 /zs+1 ≥ wi,s+1 /zs+1 ≥ wi,s /zs+1 =
∗
wi,s /zs∗ . Thus we replace zs by zs+1
in the definition of
qi,s+1 but use of either leaves its value unchanged, since
∗
by hypothesis both exceed qi,s ≤ wi,s /zi,s
.
2.4 Edge Weights. We now specify the weights used
for edge P
selection. The totalPsimilarity of node u ∈ U is
C(u) = u0 ∈U C(u, u0 ) = v∈N (u) (|N (v)|−1). Thus,
the effective contributions of an edge (u, v) to the total
similarities C(u) and C(v) are |N (v)|−1 and |N (u)|−1
respectively. This relation indicates that if we wish to
include nodes u ∈ U, v ∈ V with high total similarities
C(u) and C(v) as vertices in the edge sample, we should
include nodes with high degrees |N (u)| and |N (v)|. In
our work, we will assign an edge (u, v) the weight
(2.2)

b (u)|+|N
b (v)|
w(u, v) = |N

b (u), N
b (v) are the neighbor sets of u, v in G
bn .
where N
In Adaptive GPS, the weight wi,t of edge ei = (u, v) is
the current weight w(u, v) based on the neighbor sets
at time t. We compare with the original non-adaptive
GPS, in which wi,t = wi,i is fixed on arrival.

Theorem 2.1. Sbi,t = I(i ∈ Kt )/pi,t is an unbiased 2.5 Similarity Update Stream Estimation. Conestimator of Si,t if t → wi,t is nondecreasing for each i. sider first generation of the exact similarity Cn from the
truncated stream Kn . Each arriving edge en = (u, v)
Proof. For t ≥ i let zi,t = minj∈Kb t \{i} rj,t . Observe that contributes to C(u,0 u) through wedges (u, v, u0 ) for
b t if and only if ri,s is not the smallest priority in v ∈ N (u) ∩ N (v). Thus to compute C(u, u0 ) we count
i∈K

the number of such wedges occurring up to time n, i.e.,
Cn (u, u0 )

=

n
X

X

I(u(ei ) = u))Si−1,(u0 ,v)

i=1 v∈N (u)∩N (u0 )

(2.3)

+ I(u(ei ) = u0 ))Si−1,(u,v)



bn of Cn
By linearity, we obtain an unbiased estimate C
by replacing each Si−1,(u,v) by its unbiased estimate
Sbi−1,(u,v) . Operationally, each arriving edge ei =
bn (u, u0 ) for all edge
(u, v) generates an increment C
0
b
(u , v) in Ki , the size of the increment being the value
corresponding value of Sbi−1,(u0 ,v) , namely, 1/pi−1,(u0 ,v) .
bn (v, v 0 ) for (v, v 0 ) ∈ V × V is computed similarly.
C
Algorithm 1: Adaptive Similarity Estimate

1
2
3
4
5
6
7
8
9
10
11
12
13

14
15
16
17
18
19

20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

Input: Stream of Bipartite Graph Edges in U × V ;
Edge Sample Size m; Similiarity Sample Size n
bU , K
b V ; Estimate C
b
Output: Sample Similarity Edges K
Procedure SimAdapt(m, n)
K = ∅; z ∗ = 0 ;
Aggregate.Initialize (n) ;
while (new edge (u, v)) do
foreach (u0 ∈ N (v)) do
UpdateEdge((u0 , v), z ∗ ) ;
Aggregate.Add ((u0 , u), 1/p(u0 , v))
foreach (v 0 ∈ N (u)) do
UpdateEdge((u, v 0 ), z ∗ ) ;
Aggregate.Add ((v 0 , v), 1/p(u, v 0 ))
if |K|< m then
InsertEdge (u, v) ;
else if
w(u, v)/β(u, v) < min(u0 ,v0 )∈K w(u0 , v 0 )/β(u0 , v 0 )
then
z ∗ = max{z ∗ , w(u, v)/β(u, v)}
else
InsertEdge((u, v)) ;
(u∗ , v ∗ ) = arg min(u0 ,v0 )∈K w(u0 , v 0 )/β(u0 , v 0 ) ;
z ∗ = max{z ∗ , w(u∗ , v ∗ )/β(u∗ , v ∗ )} ;
DeleteEdge((u∗ , v ∗ ))
Procedure UpdateEdge((ũ, ṽ), z̃)
if (z̃ > 0) then
p(ũ, ṽ) = min{p(ũ, ṽ), w(ũ, ṽ)/z̃}
Procedure InsertEdge(ũ, ṽ)
foreach (u00 ∈ N (ṽ)) do
UpdateEdge((u00 , ṽ), z ∗ ) ; w(u00 , ṽ) ++
foreach (v 00 ∈ N (ũ)) do
UpdateEdge((ũ, v 00 ), z ∗ ) ; w(ũ, v 00 ) ++
K = K ∪ {(ũ, ṽ)}; w(ũ, ṽ) = |N (ũ) + N (ṽ)|; p(ũ, ṽ) = 1
Procedure DeleteEdge(ũ, ṽ)
K = K \ {(ũ, ṽ)}; Delete p(ũ, ṽ)
Procedure SimQuery()
bU ∪ K
b V , C)
b = Aggregate.Query ()
(K
Class Aggregate()
Method Initialize (n) ;
Method Add (key, value);
Method Query ;

2.6 Stream Aggregation of Similarity Updates.
The above construction recasts the problem of reconbn (u, u0 ) : (u, u0 ) ∈ U × U } as the
stituting the sums {C
problem of aggregating the stream of key-value pairs
n

o
0
bi
(u, u0 ), p−1
:
i
∈
[n],
e
=
(u,
v),
(u
,
v)
∈
K
i
i−1,(u,v)
Exact aggregation would entail allocating storage for
every key (u, u0 ) in the stream. Instead, we use samplebased aggregation to provide unbiased estimates of the
bn (u, u0 ) in fixed storage. Specific aggreestimates C
gation algorithms with this property include Adaptive
Sample & Hold [15], Stream VarOpt [16] and PriorityBased Aggregation (PBA) [17]. Each of these schemes
is weighted in the sense that large aggregates a more
likely to be retained, with inclusion of new items having probability proportional to the size 1/pi−1,(u,v) of an
update. While our algorithmic framework is agnostic to
algorithm choice, our implementation uses PBA, which
enjoys good accuracy relative to competitive methods.
Estimation Variance. Inverse probability estimators
[18] such as those occuring in Theorem 2.1 furnish
unbiased variance estimators that are computed directly
from the estimators themselves. For Sbi,t this takes the
form Vbi,t = Sbi,t (p−1
i,t −1), with the unbiasedness property
E[Vbi,t ] = Var(Sbi,t ). These have performed well in graph
stream applications [14]. The approach extends to
the composite estimators with sample based aggregates,
using variance bounds and estimators established for the
methods listed above, combined via the Law of Total
Variance. Due to space limitations we omit the details.
2.7 Algorithms. Alg. 1 defines SimAdapt, which
implements Adaptive Graph Priority Sampling for bipartite edges, and generates and aggregates a stream of
similarity updates. SimAdapt accepts two parameters:
m the reservoir size for streaming bipartite edges, and
n the reservoir size for similarity graph estimates.
Aggregation of similarity increments is signified
by the class Aggregate, which has three methods:
Initialize, which initializes sampling in a reservoir of
size n; Add, which aggregates a (key,value) update
to the similarity estimate, and; Query, which returns
the current estimate of the similarity graph at any
point in the stream. This “within stream” reporting
is supported by all stream aggregation methods listed
in Section 2.6. Similarity updates are generated for each
arriving edge, taking the form of the inverse probability
for each adjacent edge (lines 7 and 10).
The remainder of the algorithm concerns updating
the bipartite edge sample. Edges are maintained in a
priority queue K based on increasing order of edge priority, which for each (u, v) is computed as the quotient

of the edge weight w(u, v) (the sum of the degrees of u
and v) and a permanent random number β(u, v) ∈ (0, 1],
generated on demand as a hash of the unique edge identifier (u, v). The arriving edge is inserted (line 12))
if the current occupancy is less than m. Otherwise,
if its priority is less than the current minimum, it is
discarded and the threshold z ∗ updated (14). If not,
the arriving edge replaces the edge of minimum priority
(lines 16–19). Edge insertion increments the weights of
each adjacent edge (lines 25 and 27). While in principle each edge probability must be updated when zt∗
changes, since the wi,t and zt∗ non decreasing, the update pi,t = min{pi,t−1 , wi,t /zt∗ } (line (22) can be deferred until wi,t increments (lines 25 and 27) or until
pi,t is needed for a similarity update (lines 6 and 9).
We compare SimAdapt with a variant SimFixed
that uses (non-adaptive) GPS for bipartite edge sampling, and which is obtained by modifying Algorithm 1
as follows. Since weights are not updated, the update and increment steps are omitted (lines 6 and 25–
27). Edge probabilities are computed on demand as
p(u, v) = min{1, w(u, v)/z ∗ }. We also compare with
SimUnif, a variant of SimFixed with unit weights.
2.8

dataset
Rating
Movie
GitHub

Bipartite
|U |+|V | |K|
dmax
2M
6M
12K
62K
3M
33K
122K
440K 4K

davg
5
90
7

Similarity
|KU | |RU |
204M 203
1.2M 6,797
22.3M 156

Table 1: Datasets and characteristics. Bipartite graph:
|U |+|V |: #nodes, |K|: #edges, dmax : max. degree,
davg : average degree. Similarity graph: |KU |: #edges
in source similarity, |RU | # dense ranks = #distinct
weights in source similarity graph.

weights. The final storage cost of the sample is O(n),
the size of the second stage sampled aggregate.
3

Evaluation

3.1 Datasets. Our evaluations use three datasets
comprising bipartite graphs drawn from real-world applications, and that are publicly available at Network
Repository [21] 1 . Their basic properties are listed in
Table 1. In the bipartite graph G = (U, V, K), |U |+|V |
is the number of nodes in both partitions, |K| is the
number of edges, dmax the maximum degree and davg
the average degree. |KU | is the number of edges in the
source side of the similarity graph and |RU | the number
of dense ranks, i.e. the number of distinct values.
• Rating: the dataset rec-amazon-ratings. A source
vertex is an Amazon user, a target vertex is a product,
with an edge denoting that a user rated a product.
There are 2, 146, 058 users, 1, 230, 917 products, and
5, 838, 043 ratings.
• Movie: is the dataset rec-each-movie. The source
vertex is a audience member and a target vertex is a
movie. An edge denotes that an audience gives a review
of a movie. There are overall 1, 623 audience members,
61, 265 movies and 2, 811, 717 reviews. The maximum
and average node degrees are both much larger than the
other two datasets.
• GitHub: the dataset rec-github. The source vertex
is a github user and the target vertex is github project.
An edge denotes that a user is a member of a project.
There are 56, 519 users, 120, 867 projects and 440, 237
membership relations.
Finally, for these experiments, we used a 64-bit
desktop equipped with an Intel Core i7 Processor with
4 cores running at 3.6 GHz.

Implementation and Complexity.
Data Structure and Time Cost. We implement
the priority queue as a min-heap [19] where the root
position points to the edge with the lowest priority.
Access to the lowest priority edge is O(1). Edge
insertions are O(log m) worst case. In SimAdapt,
each insertion of an edge (u, v) increments the weights
of its |N (u)|+|N (v)| neighboring edges. Each weight
increment may change its edge’s priority, requiring its
position in the priority queue to be updated. The worst
case cost for heap update is O(log m). But since the
priority is incremented, the edge is bubbled down by
exchanging with its lowest priority child if that has
lower priority. Assuming uniform distribution of initial
Plog m
position, the average cost is O(m−1 h=02 2h (log2 m −
h) = O(1) where the sum is over levels h in the heap.
Space
Cost. The
space
requirement
is
b |+m + n), where |U
b |+|Vb | is the number
O(|Vb |+|U
of nodes in the reservoir, m is the edge reservoir
capacity and n the similarity reservoir capacity. There
is a trade-off between space and time, and while we
could limit space to O(m + n), the cost update per edge
would require a pass over the reservoir (O(m) worst
case). SimAdapt maintains the weight w(u, v) and
probability p(u, v) for each bipartite edge (u, v). The 3.2 Accuracy Metrics. Since applications such as
priority w(u, v)/β(u, v) is computed on demand. A recommendation systems rank based on similarity, our
hash-based pointer into the heap locates the entry of an metrics focus on accuracy in determining higher similaredge; this structure is similar to one in [20]. SimFixed
does not need this pointer since it does not update edge
1 http://networkrepository.com

Figure 2: Error Reduction with Filtering. Left: Movie, actual and forecast similarity, no filtering. Center: filter
count 5. Right: Rating. WRE for edge sample rates {1, 5, 10}%, filter counts 0, 1, 5, 10, 15.
ities that dominate recommendations with metrics that
have been used in the literature; see e.g., [22].
Dense Rankings and their Correlation. We
compare estimated and true rankings of the similarities.
Since similarity values are not unique, we use dense
ranking in which edges with the same similarity have
the same rank, and rank values are consecutive. Dense
ranking is insensitive to permutations of equal similarity
edges and reduces estimation noise. We use the integer
part of the estimated similarity to reduce noise. To
assess the linear relationship between the true and
estimated ranks we use Spearman’s rank correlation
on top-k true ranks. For each edge e in the true
similarity graph, let re and rbe denote the dense ranks of
b
C(e) and bC(e)c
respectively. Cor(k) is the top-k rank
correlation, i.e., over pairs {(re , rbe ) : e ∈ KU,k } where
KU,k = {e ∈ KU : re ≤ k}.
Weighted Relative Error. For ranking applications there is greater interest in accuracy of higher similarity edges. Hence we summarize relative errors by
weighting an average by the true edge similarity, and
for each k compute the top-k weighted relative error
P
b
e∈KU,k |C(e) − C(e)|
P
WRE(k) =
e∈KU,k C(e)

recently proposed in [13]. Several similarity metrics
are investigated in [13]; we use CnHash to denote its
CN estimate adapted to the bipartite graph setting.
CnHash uses a separate edge sample per node of the
full graph, sampling a fixed maximum reservoir size L
per full graph node using min-hashing to coordinate
sampling across different nodes in to order promote
selection of common neighbors. Similarity estimates are
computed across node pairs. Hence unlike our methods,
CnHash does not offer a fixed bound on the total edge
sample size in the streaming case because neither the
number of nodes, nor the distribution of edges is known
in advance. We attribute space costs for CnHash based
on the constant space per vertex property of the sketch
described in [13], and map this to an equivalent edge
sampling rate fm , taking account of different spaceper-edge costs of the methods. For a sample aggregate
size n, we apply our metrics to the CnHash similarity
estimates of the top-n true similarity edges. Note
[13] used indirect relative performance metrics for link
prediction applications based on the similarities.
3.4

Experiment Description.
Data Preparation. Each dataset was given in
source node order, which we rearranged random and
eliminated duplicate edges.
Sampling Rates. We applied the SimAdapt,
3.3 Baseline Comparison Methods. We compare SimFixed and SimUnif to each dataset, with the edge
against two baseline methods. First, simple takes a sample reservoir size m equal to fractions fm of the total
uniform sample of the bipartite edge stream, and forms edges, and the second stage sample aggregation reserb (u) ∩ N
b (u0 )|/p2
an unbiased estimate of C(u, u0 ) by |N
voir size n equal to fractions fn of cardinality of the
where p is the bipartite edge sampling rate.
unsampled similarity graph. Movie and GitHub used
Second, we compare with sampling-based approach fm ∈ {5%, 10%, 15%, 20%, 25%, 30%}. The larger Ratto link prediction in (non-bipartite) graph streams

similarity greatly exceeds the true similarity due to estimation noise, by as much as two orders of magnitude. These are largely absent after filtering. The right
hand plot displays the WRE in Rating for the top 100
dense ranks with fm ∈ {1%, 5%, 10%} and PBA with
fn = 10% Filtering provides an order of magnitude reduction in WRE across all sampling rates considered.
Across all datasets we most benefit was attained using a
filter count of 10, which we use for the remaining results.

Figure 3: Second Stage Sampling w/ PBA at 5% and
15%, and none. Left: WRE. Right: 1 − Cor. Right:
1-ATOP, as function of top n ranks. Dataset Movie
with filter count 10, SimFixed 10% edge sampling.

ing achieved the same accuracy with the smaller sampling rates fm ∈ {1%, 5%, 10%}. The second stage sampling fractions were fn ∈ {5%, 10%, 15%, 100%}, where
100% reservoir means exact aggregation.
Noise Reduction. The algorithms were enhanced
by two forms of noise reduction. The first averages
estimates over five runs on each data stream with the
same initial randomization. The second filters out
similarity edges for which the number of updates is less
than a specified threshold. Estimates comprising a small
number of updates are more subject to noise from the
1/p form of the inverse probability estimators, while
estimates with more updates benefit from statistical
averaging. We used threshold counts of [1,5,10,15] and
0 (i.e., no filtering). Note filtering requires an additional
counter per aggregate.
3.5 Experiment Results. In this section we report
accuracy metrics (WRE, Cor) for SimAdapt, SimFixed and SimUnif across a range of edge and similarity sampling rates, using various filter thresholds, to
the three datasets (Rating, Movie, GitHub). We first
narrow the scope of parameter exploration by establishing common filtering thresholds across the datasets.
Filtering and its Utility. Error filtering improved error metrics across many datasets, algorithms
& sampling rates. We illustrate our results in Figure 2. The left and center plots compare the effects
of no filtering (top) with filtering threshold 10 in applying SimAdapt with fm = 10% edge sample, no PBA
(fn = 100%), for approximately 1,000 similarity edges
in the top 100 estimated dense ranks. With no filtering, the noise in the true similarity curve corresponds
to a small number of similarity edges whose estimated

Figure 4: Method Comparison. Left: Movie. Right:
GitHub. Top: WRE for top-100 dense ranks as
function of edge sample rate. Middle: 1 − Cor(k) for
same. Bottom: WRE for top-k ranks as function of k
for fm = 10% edge sampling. All proposed methods
with fn = 5% PBA.
Sample-based Aggregation. In all our datasets
we found that PBA second stage has little effect in
accuracy for sampling rates down to about 10% (and less

in some cases) under a wide variety of other parameter
settings. Figure 3 shows results for SimFixed applied to
Movie at fraction fm = 10% and PBA sampling rates
of 5% and 15%, specifically WRE and 1 − Cor for the
top-k dense ranks, as a function of k. For k up to several
hundred, even 5% PBA sampling has little or no effect,
while errors roughly double when nearly all ranks are
included. SimUnif, and to a lesser extent SimFixed,
exhibited more noise, even at higher bipartite sampling
rates fm , which we attribute to a greater diversity in
the key set of updates (being less concentrated on high
similarities) competing for a fixed keyset space in PBA.
This noise was absent with exact aggregation (PBA at
100%), supporting our interpretation.
Comparing Bipartite Edge Weighting Methods. We now examine relative accuracy of SimAdapt,
SimFixed, and SimUnif. Performance as a Function of
Edge Sample Rate. Figure 4(top) displays WRE for the
top-100 dense ranks at 5% PBA as a function of edge
sample rate fm for Movie(left) and GitHub(right).
Each figure has curves for SimAdapt, SimFixed and
SimUnif (and also for baseline methods CnHash and
simple that we discuss below). Performance of SimFixed is somewhat better than SimUnif. Larger benefit is obtained for SimAdapt, up to an order of magnitude reduction in WRE for fm ≥ 20%. The middle row
of Figure 4 exhibits similar behavior for the 1−Cor(100)
metric.
Performance as a Function of Rank. Figure 4(bottom) displays WRE for top-k ranks as a function of k
at edge sample rate fm = 10% for the same data. As
expected, SimAdapt is most accurate for lower ranks
that it is designed to sample well (0.002 and 0.034 for
k = 50 in Movie and GitHub respectively, growing to
about 0.2 at maximum rank considered. In some cases
SimUnif performed slightly better at high ranks, we believe because it was directing relatively more resources
to high rank edges.
Baseline Method Comparisons Figure 4 includes metric curves for the baseline methods simple
and CnHash. SimAdapt and SimFixed typically performed better than simple by at least an order of magnitude. In some experiment with higher edge sample
rate fm , SimUnif was less accurate than simple, we
believe due to the noise described above. This is evident e.g. in Figure 4(bottom, left).
Our methods performed noticeably better than
CnHash in all cases, and while CnHash was often no
better than simple. The reasons for this are two-fold.
The first is that in the streaming context, CnHash
does not make maximal use of its constant space per
vertex for nodes whose degree is less than maximum
L. However, even counting only the stored edges,

CnHash performs worse than our methods for storage
use equivalent our edge sampling rate fm < 15%.
This brings us to the second reason: the interaction
of reservoir design with graph properties. By using a
shared edge buffer, SimAdapt and SimFixed devote
resources to high adjacency edges associated with high
similarity in a sparse graph. In the streaming context,
edges incident at high degree nodes are more likely to
acquire future adjacencies.
Summary of the Evaluations. Our evaluation
confirm the expected benefits of sampling the similarity
graph that were discussed as motivation for our work in
Section 1. With a relatively small sample of bipartite
and the similarity graph edges (10% in each case),
and with the enhancement of count based filtering of
similarity edges at threshold 10, the sampled similarity
edge set reproduces the true similarities of sampled
edges with errors of about 10−2 for our error metrics
for top-100 dense estimate ranked edges, rising to an
error of about 10−1 when most estimated edges are
considered. We finish by reporting that with above
parameters, the rank distribution properties of sampled
similarity graph are very similar to the those of the
upsampled graph for all but the highest ranks.
4

Related Work

A number of problems specific to bipartite graphs
have recently attracted attention in the streaming or
semi-streaming context. The classic problem of bipartite matching has been considered for semi-streaming
[23, 24] and streaming [25] data. Identifying top-k
queries in graphs streams has been studied in [26]. Concerning sampling methods, the Adaptive Graph Priority Sampling of this paper builds on non-adaptive GPS
proposed in [14] while the second sample aggregation
method appears in [17]. Graph stream sampling for
subgraph counting is addressed in [14, 27, 28, 29, 30]
amongst others; see [10] for a review. [13] is closer to
our present work in that it provides a sample-based estimate of the CN count, albeit not specialized to the
bipartite context. We make a detailed comparison of
design and performance of [13] with our proposed approach in in Section 3.5.
5

Conclusion

This paper has proposed a sample-based approach to estimating the similarity (or projection graph) induced by
a bipartite edge stream, i.e., the weighted graph whose
edge weights or similarities are the numbers of common
neighbors of its endpoint nodes. The statistical properties of real-world bipartite graphs provide an opportunity for weighted sampling that devotes resources to
nodes with high similarity edges in the projected graph.

Our proposed algorithm provides unbiased estimates of
similarity graph edges in fixed storage without prior
knowledge of the graph edge stream. In evaluation on
real-world graphs, our method incurs weighted relative
errors as low as 10−2 in a 10% edge sample. In future
we plan to explore other instances of our framework
with edge weights tuned to optimize estimation of other
neighborhood based similarity metrics.
References
[1] C. Lo, D. Frankowski, and J. Leskovec, “Understanding
behaviors that lead to purchasing: A case study of
pinterest,” in ACM SIGKDD, 2016, pp. 531–540.
[2] K.-I. Goh, M. E. Cusick, D. Valle, B. Childs, M. Vidal,
and A.-L. Barabsi, “The human disease network,” vol.
104, no. 21, pp. 8685–8690, 2007.
[3] D. Liben-Nowell and J. Kleinberg, “The link-prediction
problem for social networks,” J. Am. Soc. Inf. Sci.
Technol., vol. 58, no. 7, May 2007.
[4] X. Ning, C. Desrosiers, and G. Karypis, A Comprehensive Survey of Neighborhood-Based Recommendation Methods. Boston, MA: Springer US, 2015, pp.
37–76.
[5] C. Bauckhage, Image Tagging Using PageRank over
Bipartite Graphs. Berlin, Heidelberg: Springer Berlin
Heidelberg, 2008, pp. 426–435.
[6] L. Page, S. Brin, R. Motwani, and T. Winograd, “The
pagerank citation ranking: Bringing order to the web,”
1998.
[7] J. Kunegis, E. W. De Luca, and S. Albayrak, “The
link prediction problem in bipartite networks,” in Proc.
IPMU’10. Berlin, Heidelberg: Springer-Verlag, 2010,
pp. 380–389.
[8] O. Allali, C. Magnien, and M. Latapy, “Internal link
prediction: A new approach for predicting links in
bipartite graphs,” Intell. Data Anal., vol. 17, no. 1,
pp. 5–25, January 2013.
[9] M. Gao, L. Chen, B. Li, Y. Li, W. Liu, and Y.-c.
Xu, “Projection-based link prediction in a bipartite
network,” Inf. Sci., vol. 376, no. C, pp. 158–171,
January 2017.
[10] N. K. Ahmed, J. Neville, and R. Kompella, “Network
sampling: From static to streaming graphs,” In TKDD,
vol. 8, no. 2, pp. 1–56, 2014.
[11] X. Liu, L. Golab, W. Golab, I. F. Ilyas, and S. Jin,
“Smart meter data analytics: Systems, algorithms, and
benchmarking,” ACM Trans. Database Syst., vol. 42,
no. 1, pp. 2:1–2:39, November 2016.
[12] D. Liben-Nowell and J. Kleinberg, “The link-prediction
problem for social networks,” journal of the Association for Information Science and Technology, vol. 58,
no. 7, pp. 1019–1031, 2007.
[13] P. Zhao, C. Aggarwal, and G. He, “Link prediction
in graph streams,” in Proc. ICDE ’16, May 2016, pp.
553–564.

[14] N. K. Ahmed, N. Duffield, T. L. Willke, and R. A.
Rossi, “On sampling from massive graph streams,”
Proc. VLDB, vol. 10, no. 11, pp. 1430–1441, Aug. 2017.
[15] C. Estan and G. Varghese, “New directions in traffic measurement and accounting,” in Proc. ACM SIGCOMM ’2002, Pittsburgh, PA, 2002.
[16] E. Cohen, N. Duffield, H. Kaplan, C. Lund, and
M. Thorup, “Efficient stream sampling for varianceoptimal estimation of subset sums,” SIAM J. Comput.,
vol. 40, no. 5, pp. 1402–1431, Sep. 2011.
[17] N. G. Duffield, Y. Xu, L. Xia, N. K. Ahmed, and
M. Yu, “Stream aggregation through order sampling,”
in CIKM, 2017.
[18] D. G. Horvitz and D. J. Thompson, “A generalization of sampling without replacement from a finite universe,” J. of the American Stat. Assoc., vol. 47, no. 260,
pp. 663–685, 1952.
[19] T. H. Cormen, C. Stein, R. L. Rivest, and C. E.
Leiserson, Introduction to Algorithms, 2nd ed., 2001.
[20] A. Metwally, D. Agrawal, and A. El Abbadi, “Efficient
computation of frequent and top-k elements in data
streams,” in Proc. ICDT’05.
Berlin, Heidelberg:
Springer-Verlag, 2005, pp. 398–412.
[21] R. A. Rossi and N. K. Ahmed, “The network data
repository with interactive graph analytics and visualization,” in AAAI, 2015.
[22] A. Gunawardana and G. Shani, “A survey of accuracy
evaluation metrics of recommendation tasks,” J. Mach.
Learn. Res., vol. 10, 2009.
[23] S. Eggert, L. Kliemann, P. Munstermann, and A. Srivastav, “Bipartite matching in the semi-streaming
model,” Algorithmica, vol. 63, pp. 490–508, 2012.
[24] L. Kliemann, Matching in Bipartite Graph Streams in a
Small Number of Passes. Berlin, Heidelberg: Springer,
2011, pp. 254–266.
[25] A. Goel, M. Kapralov, and S. Khanna, “On the
communication and streaming complexity of maximum
bipartite matching,” in Proc. SODA ’12, Philadelphia,
PA, USA, 2012, pp. 468–485.
[26] S. Pan and X. Zhu, “Continuous top-k query for graph
streams,” in Proc. CIKM ’12, New York, NY, USA,
2012, pp. 2659–2662.
[27] M. Jha, C. Seshadhri, and A. Pinar, “A space-efficient
streaming algorithm for estimating transitivity and
triangle counts using the birthday paradox,” ACM
Trans. Knowl. Discov. Data, vol. 9, no. 3, pp. 15:1–
15:21, 2015.
[28] L. D. Stefani, A. Epasto, M. Riondato, and E. Upfal,
“TriÈst: Counting local and global triangles in fully dynamic streams with fixed memory size,” ACM TKDD,
vol. 11, no. 4, pp. 43:1–43:50, 2017.
[29] A. Zakrzewska and D. A. Bader, “Streaming graph
sampling with size restrictions,” in IEEE/ACM International Conference on Advances in Social Networks
Analysis and Mining, 2017.
[30] N. K. Ahmed, N. Duffield, J. Neville, and R. Kompella,
“Graph sample and hold: A framework for big-graph
analytics,” in SIGKDD, 2014.

