DEIM Forum 2017 D7-3

A/B Testing for Social Network Services with Directed User Graphs
Jian CHEN† and Masashi TOYODA†† Graduate School of Information Science and Technology, The University of Tokyo
4-6-1 Komaba, Meguro-ku, Tokyo, 153-8505 Japan
E-mail: †{kenn-chen,toyoda}@tkl.iis.u-tokyo.ac.jp
Abstract For social network services (SNSs) like Twitter and Facebook, when a new feature (such as the “poll”
in Twitter) is added, it is necessary to evaluate the eﬀect of this new feature. Recent works use network A/B testingfor this kind of estimation. However, existing methods regard the social network as undirected graph, in which users
always influence each other, while some SNSs such as Twitter should essentially be modeled as directed graph since
only followees can influence followers but not vice versa. In this paper, we therefore propose a new A/B testing
method for social network with directed user graph, on which we evaluate our algorithm by comparing the resultwith that of 3 baseline methods.
Key words directed user graph, social network, a/b testing, causal inferenceN)
1 ∑( ⃗AT E = E[Y (⃗1) − Y (⃗0)] =Yi (1) − Yi (⃗0)
N i=1

1. INTRODUCTION
A/B testing is the most standard and widely used method
for inferring the causal eﬀect. For example, A/B testing is
usually adopted to infer the eﬀect of a new medicine. In thiscase, patients are randomly assigned to either the treatmentgroup or the control group. Patients in the treatment groupwill take the new medicine (treated), while those in the control group will be kept unchanged (controlled). Then the
Average Treatment Eﬀect (ATE) can be obtained by comparing the diﬀerence of the average outcomes (such as theseverity of the disease) of the two groups.
However, there is a key assumption for traditional A/B(1)

where the ATE is the average diﬀerence between the outcome
under assignment ⃗z = ⃗1 and the outcome under assignment⃗z = ⃗0. However, since it’s impossible to both treat and control an experiment unit simultaneously, ATE in equation 1
cannot be computed in an A/B testing experiment. Rather,
the ATE is estimated as
1
ATˆ E =N1∑

Yi (Z = ⃗z) −{i|⃗
zi =1}1
N0∑

Yi (Z = ⃗z) (2){i|⃗zi =0}

where N1 and N0 are the number of units under treatment
and control respectively.

Here experiment units are uni-

testing that is usually called Stable Unit Treatment Value

formly sampled, which means they are randomly assigned

Assumption (SUTVA). This assumption states that the out-to either the treatment group or the control group. Then

come of every unit in the experiment only depends on its own

the estimated ATE is the diﬀerence of outcomes between theassignment (treatment or control) but not the assignments

two groups. It can be proved that the estimated ATE inof others. In the case of the above example, which intends

equation 2 will converge to the true ATE when N1 , N0 → ∞to infer the eﬀect of a new medicine, this assumption can beunder SUTVA using the Law of Large Numbers [1].

easily satisfied. On the contrary, because of the existence of

The importance of SUTVA lies in the missing of interfer-

network eﬀect, users in social network are easily influenced

ence between the treatment group and control group. But

by others, thus making the SUTVA invalid.

in social network, users can influence their friends (such as

To further explain the diﬀerence introduced by the network

Facebook) or their followers (such as Twitter) frequently,

eﬀect, we here consider about the method for obtaining thewhich poses a problem that by uniform sampling, we can

ATE under SUTVA. Let U be the set of all units in the ex-hardly find two groups in which users in one group have no

periment with |U| = N , and Z ∈ M

be the random vector

relationship with users in another group. To make this prob-

N

representing the assignments of all users, where M = {0, 1}.

lem clearer, let’s consider another example. If we designed a⃗zi = 0 means user i is under control, and ⃗zi = 1 means user

new recommendation algorithm that intends to make users

i is under treatment. We further define Yi (Z = ⃗z) as thepost (or repost) more contents in the social network, using

response (outcome) function of unit i under the assignmnet

the method we mentioned above, we could randomly selectvector ⃗z. Then the ATE is define assome users to whom we apply the new algorithm, and also

randomly select some users and don’t apply the algorithm toment and the users network exposure to control. Network

them for comparison purpose. Although we expect that the

exposure can have several definitions. For example, a user i

ATE could be estimated by the diﬀerence of the outcomes

being network exposure to treatment can be defined as userof these two groups, in fact the interference between the twoi and qd neighbors of him/her are treated, where d is thegroups can make the estimation inaccurate. Imaging that a

number of neighbors of user i and q is a predefined fractionaluser A who is being controlled follows many users who arenumber. They then used the Horviz-Thompson estimator,

treated, if the algorithm is actually eﬀective, which means

which is an unbiased estimator, for the estimation of thethe users followed by user A will post more contents to theATE, and it’s variance bound was proved to be linear to thesocial network, it is very likely that user A will also post

degree of the graph under some constraints. Gui et al. [1](repost) more contents. Thus, even though users in con-proposed a method which is also based on cluster random-

trol group are not applied the new algorithm, their posted

ized sampling. But in this method, the graph is first parti-(reposted) contents can increase indirectly due to the appli-

tioned into equal-sized clusters and the response function Yi

cation of the new algorithm to users under treatment. So theis modeled as a linear function

outcome of control group will be higher, causing the ATE tog(⃗zi , σi ) = α + β⃗zi + γσi

become smaller.

(3)

Several methods have been proposed to deal with the prob-

where ⃗zi is the treatment of user i and σi is the fraction oflem of network eﬀect for network A/B testing, and we willtreated neighbors. Once the parameters of this linear model

introduce some of them in the next section. In this paper, we
extended the network A/B testing to directed user graph byare estimated by training on the data of sampled users, theATE can be obtained as g(⃗1, 1) − g(⃗0, 0).

proposing a new sampling method, and comparing the eﬃ-

Arbour et al. [5] also proposed a method inferring thecacy with 3 baseline methods. As far as we know, we are thecausal eﬀect making use of the observational data instead

first to study the A/B testing problem specific to directedof A/B testing.

user graph.

2. RELATED WORK

3. A/B TESTINGUSER GRAPH

FOR

DIRECTED

A problem that is similar to our network A/B testing prob-

As introduced in the previous section, several methods

lem is formulated by Backstrom et al. [2] named network

have been proposed for network A/B testing for undirectedbucket testing. This problem assumes that a certain featureuser graph. In this section, we discuss about the diﬀerencein social network can be normally used by a user only if at

between directed and undirected graph for network A/B test-

least K neighbors of him/her can also use this feature. The

ing as well as the clustering methods for directed graph.

set of users satisfying this restriction is called core set, while
the set of users used for adding up the K neighbors is called
fringe set. Then under this assumption, the task is to estimate the average outcome when the feature is added to thesocial network. [2] proposed a random walk based method
to sample the core set with the tradeoﬀ of the uniformityof sampling and the size of fringe set. [3] also studied thisproblem and proposed some new algorithms with providing
the corresponding variance bound. The main diﬀerence between the network bucket testing and network A/B testing
we studied here is that network bucket testing doesn’t require

C3

the control group, and only intends to estimate the overalloutcome when all users are treated, while network A/B test-

C1

C2

ing is aimed to estimated the causal eﬀect and requires bothFigure 1: Example of the diﬀerence in clustering between

treatment group and control group.

undirected and directed graphFor network A/B testing, Ugander et al. [4] proposed amethod to first cluster the network and then randomize the3. 1 Issues for A/B Testing in Directed Graphassignment on cluster level. They also defined the network

Existing methods of network A/B testing only consider

exposure, with which ATE was obtained as the diﬀerence ofthe network as an undirected graph, in which an edge be-

the outcomes between the users network exposure to treat-

tween two users is undirected, enabling them to influenceeach other. But many social networks are directed essen-

rected graph, in which the information of directionality istially, such as Twitter and Instagram. In these directed user

maintained as the weight associated with each edge. Wegraphs, an edge is directed and represents a follow relation-

adopt this method as our baseline-2, in which we transformship. A user (called followee) is able to influence the user who

the directed graph to undirected graph by ignoring the direc-

follows him/her (called follower) but not vice verse, which

tionality, but all edges having no corresponding reverse edge

gives us an intuition that in order to incorporate the infor-

will be deleted.

mation of unidirectionality, it requires a diﬀerent clustering

Methods for clustering on undirected graph usually re-method when we use the cluster randomized sampling. As

quires an objective criterion such as modularity and nor-shown in figure 1, the graph on the top is densely connected

malized cut. So these methods can be readily extended toand it can be regarded as a single cluster, while on the bot-directed graph by taking the directionality into considera-tom, the structure of this graph is almost the same with thetion. We created baseline-3 by extending the clustering al-

top one, except that the edges become directed. However,gorithm proposed in [1], which is based on label propagation

the clustering result can be quite diﬀerent. In this directed

and tries to maximize the internal edges of each cluster in agraph, the node in cluster C3 has many out edges represent-

greedy way.

ing the follow relationship. Within cluster C1 and C2, nodes

Other methods for clustering directed graph include infor-

are strongly connected, and since the node in cluster C3 ismation theoretic based methods, probabilistic model based

not followed by other nodes, even if it is influenced by C1, it

methods, Blockmodeling methods and some others.

is not able to transmit the influence to C2, so C2 cannot be
influenced by C1. And C1 will also not be influenced by C2
for the same reason.

3. 3 Two-Step Clustering Method for Directed
User Graph
As mentioned in section 3. 1, A/B testing in directed user

In addition to the change of edge direction, the structure

graph faces two major problems. The first is that the exis-of the network can also be quite diﬀerent. In undirected user

tence of directionality of edges makes it necessary to design

graphs like Facebook, users connected with an edge are usu-

a new sampling method which incorporates this extra infor-ally friends and the number of friends of a single user cannot

mation. The second is that users who has too many followers

be too large, making it easier to partition the graph into well

will still have a lot of influence across clusters.

connected clusters. In contrast, a famous person on Twitter

The first way to extend A/B testing from undirected user

can have millions of followers. Imaging a more extreme casegraph to a directed one may be choosing a suitable cluster-that a user is so famous that everyone in the network follows

ing method for directed network as discussed in [6]. However,him/her, no matter how we partition the network, this user

the second problem as we mentioned above is still hard to be

can always influence users in other clusters. Therefore, theavoided by making use of these common clustering methods.

characteristic that some users can have a large number of fol-

The second way that seems plausible is to ignore thoselowers poses another problem for the A/B testing in directed

influential users and just sample users who don’t have toouser graph.

many followers. In this way, the influence across clusters

3. 2 Clustering Directed Graphcan indeed be reduced dramatically, and thus the treatment

In this section, we introduce some of the clustering meth-group can have much less influence on control group andods in directed networks. Malliaros et al. [6] made a compre-

vice versa. It seems that this kind of way could estimate thehensive survey about this problem. And based on them, we

ATE more accurately. However, ignoring influential users

proposed 3 baseline methods.

can bring significant bias to the estimated result. Because

The most straightforward and naive method is to trans-

by adopting this sampling method, all tested users are those

form the directed graph to undirected graph by just ignoring

who have relative small number of followers, but in the real

the edge directionality. After the transformation, a largecase that a feature is finally added to the social network

amount of algorithms proposed for undirected graphs can be(which is equivalent to that every one in the social network

directly applied. We adopt this method as our baseline-1,

is treated), influential users actually contribute a lot to thein which we first transform our directed user graph to undi-

eﬀect. Imaging that if Twitter added a new feature, howrected graph and apply the method proposed in [1]. But since

about the results between the case that most famous users

this naive method ignores the information of directionality,

use it and that no famous user uses it. The former is expected

the accuracy is expected to be low.

to make this feature more eﬀective. Therefore, sampling by

An alternative method is to transform directed graph toignoring influential users can underestimate the ATE.

undirected graph by partially maintaining the directionality.

Given the defects of the above methods, we proposed a

For example, it can be transformed to an weighted undi-

new sampling methods for directed user graph, called two-step clustering (TSC) method, which composes the following

and the average outcome of their neighbors, as well as somesteps:

user specific traits (expressed as Gaussian noise). For ev-（ 1 ） We first separate the network into two parts S1 andery users, even if the assignment and the average outcome

S2 . S1 includes influential users whose in-degrees are aboveof neighbors are the same, the outcome can still be diﬀerent

the threshold D, and the rest constitutes S2 .

due to some other factors, such as the personality, age, etc.

（ 2 ） Then we cluster on S1 using the same clustering

So the term (user specific traits) is add to capture this kind

method as in baseline 3.

of noise. In this model, λ0 is the intercept (set as -1.5 in this（ 3 ） For users in S2 , they are included in one of the clus-

experiment). ⃗zi ∈ {0, 1} is the assignment of user i and λ1

ters obtained in the previous step by majority vote. Moreis the strength of the treatment eﬀect; A is the adjacency

specifically, a user in S2 will be included to the cluster thatmatrix of the directed network and di is the out-degree ofmost his followees belong to.

user i, so（ 4 ） Finally, we randomly give the assignment (treat-user i, and λ2 is therefore the strength of the network eﬀect.

ment or control) to each cluster with equal probability.

Ui,t ∼ N (0, 1) captures user specific traits.

Ai· Yt−1
diis the average outcome of the followees of

The final outcome can be obtained by setting Yi,0 = 0 and

4. EXPERIMENTS

then iteratively running equation 4. In our experiment, we

One of the main problems of A/B testing is that there isno ground truth for the ATE, which means it is impossible
for us to evaluate our estimation result in a real A/B testing

iteratively run it 5 times.
We use the same estimator as in equation 3, but the σinow means the proportion of the treated followees.

experiment. Therefore, we instead use an outcome model to

4. 3 Experiment Settings

simulate the outcome process.

In order to evaluate the eﬃcacy of our proposed method

4. 1 Datasets

for A/B testing in directed user graph, we compared it with

Our experiments are conducted on three real directed net-

3 baselines we setup in section 3. 2. For clarification purpose,works from [7] and one synthetic directed network. These

we again list the baselines here:•

networks are shown as below.

Baseline-1: transforming directed graph into undi-（ 1 ） Wikipedia vote network

rected one by ignoring the directionality of the edge andThis dataset contains the voting data of Wikipedia, in whichthen applying existing method for undirected graph.

administrators vote for promoting users to adminship and it•

Baseline-2: transforming directed graph by first delet-

has 7115 nodes and 103689 edges. An directed edge repre-

ing edges without a reverse edge and then ignoring the direc-

sents a vote relationship.

tionality, and finally applying existing method for undirected（ 2 ） Epinions social network

graph.

This dataset is from a consumer review site Epinions.com.

•

Baseline-3: extending the clustering algorithm in [1]An edge in this network represents a user trusts another user.

to partition directed graph and then directly estimating on

And this data set contains 75879 nodes and 508837 edges.

this directed graph.

（ 3 ） Slashdot social network, November 2008

Since there is no ground truth for real A/B testing experi-This dataset is from a technology-related news website slash-ments, we here use the outcome model expressed as equation

dot.org and an edge from user i to user j means user i tagged

4 to generate synthetic outcome data based on the structureuser j as a friend or foe. This data set contains 77360 nodesof the network and the assignment. The true ATE can be

and 905468 edges.

computed as（ 4 ） Growing Network

This is a synthetic growing network with 20,000 nodes.
4. 2 Outcome Model and Estimator

AT E =N)
1 ∑(Yi,5 (Z = ⃗1) − Yi,5 (Z = ⃗0)
N i=1

(5)

Our outcome model is similar to that in [1] except that wewhere N is the number of users in the network and the out-

extended it to directed network and changed the outcome

come will be generated by iteratively running the outcome

from binary value to non-negative real number. And themodel 5 times. Then we will use our proposed method (TSC)model is expressed as

and 3 baseline methods to estimate the ATE, and finally we

Yi,t (Z = ⃗z) = λ0 + λ1 ⃗zi + λ2

Ai· Yt−1+ Ui,tdi(4)will comparex them based on Rooted Mean Square Error(RMSE) of the estimated ATE.

where Yi,t is the response function that returns the outcome

4. 4 Experiment Resultof user i at time t. This response function is modeled as

The results are shown in figure 2. In our experiment, λ1

a linear function of the assignment of the user themselves

was set to 0, 0.25, 0.75, 1, and λ2 was set to 0, 0.1, 0.5, 1. From(a) Wikipedia vote network(b) Epinions social network(c) Slashdot social network, November 2008(d) Growing Network

Figure 2: The results for comparing TSC with baseline methods on diﬀerent directed graphs

the results, we have the following observations.

figure 3, in which we sort the clusters by their sizes and only

For all directed user graphs, the RMSE grows when we in-

the top 20 clusters are drawn in this figure. It’s easy to see

crease λ2 (the strength of network eﬀect) or λ1 (the strengththat the diﬀerences among clusters in the other three graphsof treatment eﬀect).

are not so significant as that in the ‘Epinions social network’,

The performance of the 3 baseline methods is almost thein which the biggest cluster is 6 times bigger than the second

same, among which baseline 3 is slightly better than the

biggest one. As a result, most nodes are in the same cluster,other two mthods. Since baseline 3 incorporates more direc-

causing the error of the estimation being greater.

tional information in the clustering algorithm, it’s reasonable
that it outperforms baseline 1 and baseline 2.

5. CONCLUSION AND FUTURE WORK

Except for the ‘Epinions social network’, the TSC method

Our proposed method, two-step clustering method (TSC),

outperforms all the baseline methods. This shows the eﬃ-

not only takes the directionality of edge into consideration,cacy of our proposed method.

but also tries to reduce the cross influence of influential users.

However, the TSC method performs poorly for ‘Epinions

And as confirmed by our experiment, the TSC method pro-social network’, and the RMSE doesn’t change a lot when weduces the best results compared with the other three baselineincrease the strength of network eﬀect (λ1 ). This is caused

methods in most occasions.

by the significant diﬀerences among the sizes of the clusters

However, for some graphs such as ‘Epinions social net-

obtained by the TSC. The sizes of the clusters are shown in

work’, the performance of the TSC can be poor. Therefore,Figure 3: The cluster sizes of each cluster partitioned by the
TSC method

we plan to improve the clustering algorithm to solve thisproblem and make it more robust.

References[1] Huan Gui, Ya Xu, Anmol Bhasin, and Jiawei Han. Network
a/b testing: From sampling to estimation. In Proceedingsof the 24th International Conference on World Wide Web,
pages 399–409. ACM, 2015.
[2] Lars Backstrom and Jon Kleinberg. Network bucket testing. In Proceedings of the 20th international conference on
World wide web, pages 615–624. ACM, 2011.
[3] Liran Katzir, Edo Liberty, and Oren Somekh. Framework
and algorithms for network bucket testing. In Proceedingsof the 21st international conference on World Wide Web,
pages 1029–1036. ACM, 2012.
[4] Johan Ugander, Brian Karrer, Lars Backstrom, and Jon
Kleinberg. Graph cluster randomization: Network exposure to multiple universes. In Proceedings of the 19th ACM
SIGKDD international conference on Knowledge discovery
and data mining, pages 329–337. ACM, 2013.
[5] David Arbour, Dan Garant, and David Jensen. Inferring
network eﬀects from observational data. In Proceedingsof the 22Nd ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining, KDD ’16, pages
715–724, New York, NY, USA, 2016. ACM.
[6] Fragkiskos D Malliaros and Michalis Vazirgiannis. Clustering and community detection in directed networks: A
survey. Physics Reports, 533(4):95–142, 2013.
[7] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford
large network dataset collection. http://snap.stanford.edu/data,
June 2014.