Semi-Data-Driven Network Coarsening

1 Introduction

Network coarsening refers to collapsing similar nodes and edges in a network so that the size of the network can be significantly reduced [Karypis and Kumar, 1998]. With massive data generated from online social networks, it is challenging to perform complicated network analysis on social networks. Network coarsening provides a new tool for big social network analysis by condensing a big network into a smaller approximating one without much loss of information.

Existing studies on network coarsening assume that network structures are known in advance and they merely focus on using popular network metrics, such as edge-cut based [Dhillon et al., 2007], link based [Mathioudakis et al., 2011], and heavy-edge-matching based [Karypis and Kumar, 1998]. In particular, a recent work [Purohit et al., 2014] studies graph coarsening by grouping similar nodes together to find a succinct representation of subgraphs. However, all these models are based on static network structures.

⇤C. Zhou is the corresponding author, zhouchuan@iie.ac.cn.

On the other hand, dynamic network structure analysis has been widely studied in recent years, which refers to networks that either evolve by time (i.e., new links are continuously formed and existing links get obsolete) [Sun et al., 2014; Bhat and Abulaish, 2015] or different subsets of links are activated at different time windows [Rodriguez et al., 2011]. Many data-driven models [Rodriguez et al., 2011; Cui et al., 2013; Du et al., 2014] have been proposed to enable dynamic network analysis by building maximum likelihood estimation models on information spreading data. However, existing data-driven approaches neglect the fact that static network structure data can be also beneficial for learning when the network is large and the training data set is relatively sparse.

Motivated by the above observations, we study in this paper a new problem of network coarsening which embeds both static network structures and dynamic network information spreading data. The basic idea is that if two nodes tightly connect with each other and co-occur frequently in the same information cascade, they are likely to be combined together. Because of the heavily skewed degree distribution in networks and a large portion of edges and nodes are relatively unimportant for network analysis [Purohit et al., 2014], we aim to find a smaller equivalent network to describe the original large yet sparse network. Based on the smaller representation, sophisticated network analysis can be solved efficiently.

In deed, learning from both static network structures and dynamic information spreading data is a very challenging problem, including 1) Network structure data and network information spreading data are heterogeneous data that need to be modeled jointly; and 2) Combining two different data sources for network coarsening leads to a complicated optimization problem which requires efficient algorithm.

To address the challenges, we propose a semi-data-driven network coarsening approach (Semi-NetCoarsen for short) to condense the networks. The corresponding learning function is constructed by simultaneously minimizing the graph regularization on the static network structures and maximizing the network coarsening likelihood on information spreading data (Challenge #1). We prove that the learning function is convex and the Accelerated Proximal Gradient algorithm is adapted to obtain the global optima (Challenge #2). Moreover, as a case study, we conduct the influence maximization analysis on the coarsened network. Experiments on both synthetic and real-world data sets demonstrate the algorithm performance.

2 Preliminaries

Information Spreading data: In a network G := (V↪E↪W), where V denotes the nodes set, E the edges set and W the weighted adjacency matrix, assume that a message c propagates through the network and leaves a trace of passed nodes ui 2 V at time stamp ti, denoted by (ui↪ ti)c. An information spreading cascade tc can be denoted by a N-dimensional vector tc := (tc1 ↪ ▷ ▷ ▷ ↪ tcN ), where tci 2 [0↪ T c ] [ ¶1♦. The symbol 1 labels nodes that the message does not reach during the observation window [0↪ T c ], in which T c corresponds to the underlying temporal dynamics [Rodriguez et al., 2011]. A collection of cascades is denoted as C := ¶t1 ↪ ▷ ▷ ▷ ↪ t♣C♣ ♦.

Similar Nodes: Given a network G and a collection of cascades C, if nodes i and j tightly connect with each other with higher Wi↪j and Wj↪i, and also co-occur frequently in the same cascade tc , we call nodes i and j as similar nodes.

Supernodes and Superedges: Given a coarsened network Gcoarsen := (V 0 ↪E0 ↪W 0 ), m 2 V 0 represents a supernode, and e 2 E0 represents a superedge. The node set V 0 is obtained by merging all the similar nodes. The edge set E0 is obtained by inferring theweighted adjacencymatrixW 0 from the coarsened network.

In this paper, we merge similar nodes under two assumptions: 1) One-time merge. A pair of nodes can be activated for the network coarsening operation by only one time. If the merge does not succeed, the nodes will not be merged ever after; and 2) One-way merge. In a cascade tc , given two nodes j and i, if tcj < tci , we merge node i into node j because node j is more likely to be the information source of the message c in terms of i.

3 ProblemFormulation

3.1 Problem Statement

Given a network G, a collection of cascade data C, and a network coarsening rate 0  ↵ < 1, the proposed Network Coarsening aims to infer a smaller coarsened network Gcoarsen by finding and merging the nodes that both tightly connect each other in the adjacency matrix W and frequently appear together in the cascade data C, with ♣V 0 ♣ = (1-↵)♣V ♣.

3.2 Principle

For a given ↵, we merge similar nodes and edges and remove redundant ones to obtain the coarsened network that contains K nodes, where K = (1 - ↵)N. Thus, the node i in G is eventually merged into a supernode s. The supernode can be regarded as a cluster with label ls. All the nodes in s are labeled as ls. The aim of network coarsening is to predict the class labels assigned to each node in G.

Given a non-negative vector yi = [yi↪1↪ ▷ ▷ ▷ ↪ yi↪K]T that denotes the distribution of class labels of the ith node, where yi↪m 2 (0↪ 1) represents the probability of node i being merged in the supernode m. The edge coarsening is determined accordingly by the merging of nodes. Assume Y = [y1↪ y2↪ ▷ ▷ ▷ ↪ yN]T 2 RN⇥K , which models the class label distribution of all nodes of G. The key point is to optimize Y to ensure that nodes from the same class label are grouped together into the same supernode. Thus, if two nodes i and j are similar, yi and yj are more likely to be the same.

After defining the label distribution matrix Y , we formulate the learning objective function that maximizes the network coarsening likelihood on the network cascade data C and minimizes the graph regularization on the prior network structure data W. By solving the learning function, we can obtain the optimal Y ⇤ , based on which we deliver the coarsened network Gcoarsen.

3.3 Network CoarseningModel

Modeling Dynamic Information Spreading Cascades

If two nodes i and j co-occur frequently in the same cascade tc , they are likely to be coarsened together, i.e., they have close distribution yi and yj. yT i yj is adopted to measure their similarity [Cai et al., 2011].

Definition 1. (Node Merging Status)

For cascade tc , if tcj < tci , we call node j as node i's parent and node i as node j's child. For the child node in an observation window T c , the result of the merging status is binary, i.e., either merged or unmerged by a parent. For the child node outside T c , the result of its merging is unmerged.

Let f c j↪i = f(tci ♣tcj ; yT i yj↪ σc) be the probability density function that describes the conditional likelihood of merging node j and node i (tcj < tci ). The MLE of σc is 1◁∆t, where σc is the diffusion speed and ∆t is the average information propagation delay time between two neighboring nodes in tc [Wang et al., 2014]. Specifically, we use exponential distribution to model f c j↪i , where f c j↪i = (yT i yj +σc) · exp(-(yT i yj + σc)(tci - tcj )). For the given f c j↪i , the symbol P(tcj ! tci ♣f c j↪i ) denotes the probability that node j merges node i.

From Definition 1, the unmerged status of node i towards one of its parents j denotes that label li is very different from lj. By contrast, the merged status denotes that li is close to lj. Thus, the label distribution of nodes of G can be determined by the node merging status.

Given cascades data C, assume the independent cascade with respect to the network coarsening process, let Qtc2C l(tc ; Y↪ σc) represent the network coarsening likelihood. l(tc ; Y↪ σc) denotes the likelihood in terms of cascade tc , which is calculated by combining the coarsening likelihood of all the nodes, which is divided by T c ,

where l(tc>T c ; Y↪ σc) is the likelihood function shown in Eq. (3) in terms of the cascade tc>T c = (tc1 ↪ ▷ ▷ ▷ ↪ tcN ♣tci > T c ), which denotes that nodes outside T c haven't been merged by any parents. l(tcT c; Y↪ σc), calculated in Eq. (2), denotes the network coarsening likelihood in terms of the cascade tcT c = (tc1 ↪ ▷ ▷ ▷ ↪ tcN ♣tci  T c ) for the given T c .

Obviously, l(tcT c ; Y↪ σc) in Eq. (2) can be decomposed into

c

two parts: 1) the first part is the nodes (in unmerged status) observed in the window T c that have not been merged by any of its parents; 2) the second part is the nodes (in merged status) observed in T c that have been merged by one of its parents, as shown in Fig. 1. Thus, the likelihood of the first part can be calculated as Eq. (4). Considering that the likelihood of a node being merged can be calculated by combining the probability of each its potential parent initializing the merge operation, thus, the likelihood of the second part is calculated as Eq. (5). Therefore, l(tcT c; Y↪ σc) in Eq. (2) can be computed by multiplying Eq. (4) and Eq. (5).

Thus, Eq. (1) can be represented as,

Modeling Static Network Structures

If two nodes i and j tightly connect with each other, they will have high probability to share the same class label (i.e., graph regularization [Zhou et al., 2005; Gu and Han, 2011]). The problem can be formulated as a graph clustering problem where the graph Laplacian can be taken as an effective tool.

We use kyi - yjk2 to measure the "dissimilarity" between yi and yj [Cai et al., 2011]. The formulation of graph regularization R(Y↪W) for network coarsening is shown in Eq. (7). Due to the fact that the closeness of yi and yj is symmetric, in this case, if Wi↪j 6= Wj↪i, we use the larger one to measure the connection between node i and j.

where the matrix D is a diagonal matrix with entries being the row sums of W, Di↪i = Pj Wi↪j, and U is the graph Laplacian [Chung, 1997] given by U = D - W.

3.4 Node Label Distribution Learning Function

In this paper, we maximize the network coarsening likelihood Qtc2C l(tc ; Y↪ σc) based on the dynamic network cascade data C, together with minimizing the graph regularization R(Y↪ W) based on the static network structure data W.

The maximum likelihood estimation (MLE) of Y is a solution to minY - Ptc2C logl(tc ; Y↪ σc). In addition, as a node in G is merged into only one supernode, it is expected that Y·i and Y·j is orthogonal, where i 6= j. We set constraints as Y T Y = I to ensure the above conditions. Meanwhile, the row vector Ym· is expected to be sparse. Thus, the network node label distribution learning function is formulated as

To solve the above problem efficiently, we relax the equality constraint as follows,

where λ, λy and ⇢ are non-negative parameters. When λ = 0, the model degenerates to data-driven method that only models the network coarsening process on the cascade data C.

Theorem 1. The problem in Eq. (9) is convex and the global optima can be obtained by using gradient-based algorithms.

Obviously, the first term of the negative likelihood function -logl(tc ; Y↪ σc) is convex, and the other three regularization terms Tr(Y T UY ), kY k1 and kY T Y - Ik2F are also convex, so the function is jointly convex.

4 The Semi-Data-Driven Framework

We first learn the optimal solution Y ⇤ to the objective in Eq. (9) in Section 4.1. Then, we use the optimal Y ⇤ to obtain the coarsened network Gcoarsen by applying the semi-datadriven network coarsening framework in Section 4.2. As a case study, in Section 4.3, we solve the influence maximization on the coarsened network Gcoarsen.

4.1 Node Label Distribution Learning Algorithm

In this work, we adapt the Accelerated Proximal Gradient (APG) [Beck and Teboulle, 2009] to learn the optimal node label distribution Y ⇤ . Let ⌘(Y ) = - Ptc2C logl(tc ; Y↪ σc) +

Algorithm 1: Network Node Label Distribution Learning

The derivative of ⌘ is denoted as r⌘ which is Lipschitz continuous on Y , kr⌘(Y ) - r⌘(Z)k  Lf kY - Zk, Z 2 S+ N , where S+ N is N⇥K non-negative matrix. Given Z, for L > 0, the quadratic approximation of F (Y ) can be defined as,

where G = Z - 1L r⌘(Z). To minimize QL(Y↪Z) with respect to Y , it is reduced to solve the following pL(G) by ignoring the constant terms in Z:

Then, the solution of Eq. (12) is pL(G) = UDiag((⌧ - λy◁L)+)V T [Toh and Yun, 2010], where G = U⌃V T , ⌃ = Diag(⌧), ⌧ 2 Rq is the vector of positive singular values arranged in a descending order and x+ = max¶x↪ 0♦. We use 0 to replace the negative entries in Y . The parameter learning is shown in Algorithm 1.

In experiments, we empirically set γ = 0▷4, ✏ = 0▷001, and Lf = 10-6NNc, where Nc is the cardinality of C.

4.2 The Semi-NetCoarsen Algorithm

Algorithm 2 lists the steps of the network coarsening method Semi-NetCoarsen. Given an upper bound of ↵, the network is coarsened by merging ↵N nodes. Based on Y ⇤ , for each node i, we merge i into the supernode m with the largest yi↪m, where m = argmaxk ¶yi↪k♦↪ k = 1↪ ▷ ▷ ▷ ↪ (1 - ↵)N.

Next, based on the previous work [Purohit et al., 2014], we use the following principle to assign new weights between supernodes. Let y0s denote the label distribution of the node s in the node merging process, y0s = Pk y⇤ k n , where n is the

Input: Network G, cascades C, the coarsening rate ↵ Output: The coarsened network Gcoarsen 1 V 0 = ;; Network coarsening based on Eq. (9) 2 Update label distribution matrix Y ⇤ using Algorithm 1 3 for i = 1 to N do 4 Assign label lm to node i with m argmaxk ¶y⇤ i↪k ♦ 5 V 0 ¶lm♦ [ V 0 6 while (♣V 0 ♣ < K) do 7 for j = 1 to K do 8 if lj ◁2 V 0 then 9 i argmaxi ¶y⇤ i↪j ♦, c = 2 10 while (li labels only one node) do 11 i the row-coordinate of c-th larger of j-th column in Y ⇤ ; c = c + 1 12 Assign label lj to node i 13 Update V 0 (remove i from the previous labeled class); V 0 ¶lj♦ [ V 0 14 for (Each pair of supernodes s1 and s2 in V 0 ) do 15 Assign weights to s1 ! s2 and s2 ! s1 16 return Gcoarsen

number of node k that has beenmerged into s. We also denote i (v) (respectively o (v)) as a set of in-neighbors and outneighbors [Purohit et al., 2014] of a node v. Let viu = Wu↪v and vou = Wv↪u denote the weight of the corresponding edges. If nodes a and b are merged into a new node c, the edge weight cit is defined in Eq. (13). cot is corresponding defined.

Complexity Analysis: It takes O(NcNK) time to model the network coarsening process and assign labels to nodes. In the coarsening process, merging node i and j takes time O(deg(i) + deg(j)) = O(n✓), where n✓ is the maximum degree of any nodes at any time. To sum up, the total worstcase time complexity of Algorithm 2 is O(NcNK +↵Nn✓).

4.3 Semi-NetCoarsen Influence Maximization

As a case study, we show how to apply the network coarsening approach Semi-NetCoarsen to the well studied influence maximization [Lu et al., 2015; Zhou et al., 2015], which aims to select the most influential nodes to maximize the spread of influence. The coarsened network is expected to approximate the original network and speeds up the calculation. Specifically, we design a framework CFSInflu based on the SemiNetCoarsen algorithm, including the following main steps.

• ÷ Coarsen the network: Given cascades data C, we coarsen the large original network G using the proposed algorithm Semi-NetCoarsen to obtain a coarsened network Gcoarsen. A mapping function ! : G ! Gcoarsen from nodes in G to that in Gcoarsen is required.

• ÷ Find the most influential nodes: Find the most influential k nodes s1↪ ▷ ▷ ▷ ↪ sk in Gcoarsen to maximize the spread of influence. A ranking function rank(s) that ranks the supernode s of Gcoarsen, in terms of the number of nodes of G merged in s, is required. We select the nodes s1↪ ▷ ▷ ▷ ↪ sk based on rank(s) which gives the top-k answers as the seed nodes of Gcoarsen.
• ÷ Select the most influential nodes in G: Given the seed node si in Gcoarsen, we select a node v 2 !-1 (si) in G as a new seed. We should select v for v = argmaxu2!-1 (si) (σ(u)), where σ(u) is the expected influence function of node u. Based on the network coarsening process, we select a seed v with the maximal value of I(v) = Pmi=1 σi(v) m from !-1 (si), i▷e▷, s0i = argmaxv2!-1 (si)I(v), where σi(v) denotes the number of nodes generated from v in the cascade ti , and m denotes the number of cascades generated from v.

Note that "coarsen the network, solve the problem in the coarsened network, and then project the solutions back towards the original graph", can be applied to other social analysis [Karypis and Kumar, 1995; Purohit et al., 2014].

5 Experiments

We evaluate the effectiveness of the proposed SemiNetCoarsen approach on both the synthetic and real-world data sets. All experiments are conducted on a Linux system with 6 cores 1.4GHZ AMD CPUs and 32GB memory.

5.1 Data Sets

For synthetic data, we consider the Kronecker graph model [Leskovec et al., 2010] with a parameter matrix [0▷9↪ 0▷1; 0▷1↪ 0▷9] to generate synthetic Kronecker data, and the Forest Fire model [Barab´asi and Albert, 1999] to generate FFire data with forward burning probability 0▷2, backward burning probability 0▷17. For real-world data, we collect Twitter data 1 [Zhang et al., 2013]. Following the work [Wang et al., 2014], we select users with a large number of friends (213 friends in our work) as the nodes and extract their social connections as edges. For each tweet record, we extract its diffusion path after eliminating all the isolated nodes and edges. Table 1 gives the statistics of the data sets.

5.2 Experimental Settings

As the network coarsening rate ↵ increases, the network is condensed smaller. With randomly selected k nodes, if the influence spread of the selected k nodes in the original network is the same as that in the coarsened network, then the network is taken as accurately coarsened.

Given a node set S, for the original and coarsened networks, we calculate the expected number of influenced nodes under the Independent Cascade model [Goldenberg et al., 2001]. Specifically, for each influenced supernode m, let C(m) represent a set of cascades generated fromm. We uniformly sample one cascade from C(m) to calculate the expected number of influenced nodes G(m) which have been merged into m. We repeat the process by 100 times and report the average results. We repeat to randomly select the seed sets S by 100 times. Thus, we obtain the average result Gc(S) for Gcoarsen and G(S) for G.

1 http://aminer.org/billboard/Influencelocality

Metrics

We use two metrics to evaluate the performance, 1) the running time; and 2) the average influence spread error rate E(S), which is calculated as E(S) = 1n Pni ♣Gc(S)-G(S)♣ G(S) . n is set to 100. The smaller E(S) is favored in comparisons.

Baseline Methods

We implement the following methods for comparisons.

• ÷ Random: A random network coarsening algorithm that randomly chooses node pairs for join.
• ÷ CoarseNet: A recent network coarsening method based on static network structures [Purohit et al., 2014].
• ÷ Data-driven: A data-driven approach that only uses information cascade data C for network coarsening.

Parameter Setup

The parameter λ is searched from λ 2 ¶0▷1↪ 1↪ 10↪ 100♦, λy is searched from λy 2 ¶0▷01↪ 0▷1↪ 1♦, and ⇢ is selected from ⇢ 2 ¶0▷01↪ 0▷1↪ 1♦. The parameters are tuned by the smallest E(S) on a sub-graph with 1,000 nodes and 2,000 cascade data for each dataset when ↵ = 0▷5. Table 2 reports the results.

5.3 Experimental Results

Fig. 2 reports the results under the metrics with varying ↵ from ¶0▷3↪ 0▷4↪ 0▷5↪ 0▷6↪ 0▷7♦, in which we randomly select 20 source nodes, ♣S♣ = 20. From Fig. 2, we have the following observations. 1) The average influence spread error rate of Semi-NetCoarsen is much smaller than the baselines, and shows robustness and consistency across both synthetic and real-world datasets. For example, for the Twitter dataset when ↵ = 0▷3, the result of Semi-NetCoarsen is 0▷0214, while it is 0▷0911, 0▷1802, 0▷6029 respectively for Data-driven, CoarseNet and Random method. The main reason is that our method embeds both the static network structure and dynamics occurring on the network (i.e., information cascade). 2) The Semi-NetCoarsen method uses more time than its peers, which is a trade-off between the mean influence spread error rate and running time. 3) To sum up, our

10 5

method outperforms baseline methods in terms of accuracy without significantly raising time cost.

5.4 Influence Maximization: ACase Study

We implement the following influence maximization methods for comparison with the CFSInflu method proposed in Section 4.3: Random-based, CoarseNet-based [Purohit et al., 2014], Data-driven-based, InfluLearner-based [Du et al., 2014] and PMIA [Chen et al., 2010]. Among these baselines, the InfluLearner-based and PMIA approaches are carried out directly on the original networks. The rest three approaches work on the coarsened networks based on the corresponding network coarsening methods.

Fig. 3 reports the experimental results, where we vary ↵ from ¶0▷3↪ 0▷4↪ 0▷5↪ 0▷6↪ 0▷7♦ (the number of seeds k = 20), and k from 1 to 30 (↵ = 0▷5). Due to the limited space, we only report the results on the Twitter dataset.

With respect to influence spread metric. The InfluLearnerbased and PMIA methods directly work on the original networks, and thus obtain the best results. Fig. 3(c) shows that the influence spread derived from the proposed CFSInflu method approximates the result on the original network. Meanwhile, CFSInflu method outperforms all the baseline methods that conducted on the coarsened networks.

With respect to running time. When more pairs of nodes are merged, the coarsened graph is smaller. Thus, the supernodes in Gcoarsen can be found faster and we can conduct the influence maximization analysis efficiently on the coarsened network. For example, Fig. 3(b) shows that the running time of the CFSInflu method drops with increasing ↵. Furthermore, Fig. 3(d) shows our method can obtain about 100 ⇥ speedup based on the coarsened network. we can conclude that our method runs orders of magnitude faster than the InfluLearner-based or PMIA methods while maintaining the influence spread results.

6 Conclusions

In this paper, we propose a new semi-data-driven framework Semi-NetCoarsen to study the network coarsening problem by both maximizing the network coarsening likelihood on the dynamic information cascade data and minimizing the graph regularization on the static network structure data. We apply the coarsened network to conduct case study on influence maximization analysis. Experiments and comparisons on both synthetic and real-world data demonstrate the effectiveness of the proposed method.

Acknowledgments

We would like to thank the anonymous reviewers for their valuable comments and suggestions. This work was supported by the 973 project (No. 2013CB329605), NSFC (No. 61502479 and 61370025), Strategic Leading Science and Technology Projects of CAS (No. XDA06030200), and Australia ARC Discovery Project (DP140102206).