HID: Hierarchical Multiscale Representation Learning for Information Diffusion

1 Introduction

The accurate prediction of information diffusion is beneficial to a wide range of applications. For instance, it may help in modeling user behavior such as clicks and commenting, so that user interest is better captured in recommender systems [Leskovec et al., 2007; Xian et al., 2019]. It can also support persuasion campaigns targeting public opinion [Nadeau et al., 2008], and bring similar advantages to other tasks such as influencer identification and viral marketing [Guille et al., 2013]. Information diffusion is an incredibly well-studied topic. While traditional stochastic probabilistic-based models dominated for many years [Kempe et al., 2003; Leskovec et al., 2007], recent advances include deep diffusion models [Wang and Li, 2019; Yang et al., 2019], which benefit from their robust generalization abilities. Nevertheless, how to accurately represent the users to better capture the process of information diffusion remains well-known as a difficult problem [Wang et al., 2019]. Specifically, whether and when a user is likely to adopt a specific piece of information may depend on a multitude of complex interactions, of which the ultimate cause remains unknown [Guille et al., 2013]. To tackle this, existing deep models tend to adopt user representation learning. In this paper, we propose a novel framework (Fig. 1) for these models that boosts their performance and learning efficiency.

In particular, our work is motivated by the importance of the user's role in the information diffusion process [Wang et al., 2019]. In order to capture the user diffusion behavior, previous works either devise complex custom models [Feng et al., 2018], or rely on external knowledge such as the friendship network and user profile [Yang et al., 2019; Lagnier et al., 2013], which is often less organized, anonymous, or inaccessible due to privacy policies [Mano and Ishikawa, 2010]. Therefore, we seek to exploit the traces of the user diffusion behavior themselves (i.e., diffusion paths), from which we extract multiple aspects of user behavior. The idea draws inspiration from recent achievements that multiscale modeling has made on various machine learning tasks [Alber et al., 2019]. Data from the real world can naturally be encoded at multiple scales, which can serve as rich and reliable resources for feature representations in deep learning. There is an urgent need for the deep models to exploit these implicit multiple scales. However, the exploration of multiscale modeling in information diffusion has largely been neglected. Against this background, we explore multiscale modeling in a user representation learning framework. The challenges are mainly three-fold: (1) how to discover and induce multiple scales, and at the same time preserve the individual behavior patterns in the original data while the scales are implicit; (2) how to transfer knowledge among multiple scales in an efficient and effective way; and (3) how to design generalizable strategies that apply to most state-ofthe-art diffusion models.

To address the above-mentioned problems, we propose the Hierarchical Information Diffusion (HID) framework. Our method has several appealing properties, most notably:

• HID aids the learning of user representations, with multiple scales of summarization over the diffusion paths. This is accomplished through upscaling, by means of grouping the users and then coarsening the diffusion paths at each scale. A k-order diffusion proximity matrix is proposed to support this. Fewer users and activities at the coarsened scale also brings about efficiency.
• Downscaling achieves an exchange of knowledge about users across scales, inspired by studies on artificial neu-

ral networks revealing that the importance of a neuron for the model performance correlates with the extent to which its weight distribution after training differs from the initialization [Meyes et al., 2019].

• Combining upscaling and downscaling yields a hierarchical learning framework that has the potential to group inactive users with others, so that more cycles of optimization are gained for the inactive users compared to sampling-based optimization without multiscaling.

Contribution. We propose HID 1 for information propagation in online networks. To the best of our knowledge, this is the first method to integrate user representation learning and multiscale modeling. HID captures the multiscale information adoption proximity between users, and can be layered on top of all existing information diffusion techniques with a user vector representation learning component. Through extensive experiments, we showcase the benefits of multiscale learning on 3 real datasets. Our method yields substantially higher predictive power and learning efficiency, and achieves empirical gains of up to 14.76%MAP score.

2 RelatedWork

Information Diffusion with User Representations. [Bourigault et al., 2014; Bourigault et al., 2016; Gao et al., 2017] utilize representation learning to predict unseen diffusion. [Feng et al., 2018] further consider network structure and user interest similarity. [Singh et al., 2017] learn user representations with a novel path sampling procedure to gather contexts for each user. [Wang et al., 2019] learn network regularized role-based user representations. [Zhang et al., 2018] learn user embeddings while regularizing the information diffusion process using community structures. [Yang et al., 2018] employ an attention mechanism and convolutional network with a user embedding layer. [Wang et al., 2018] employ a recurrent network with a user embedding layer and explore both diffusion paths and graph by structure attention.

1 https://github.com/hongluzhou/HID

Multiscale Representation Learning. Multiscale representation learning for information diffusion is unexplored. [Yang et al., 2019] jointly handle both micro- and macroscopic prediction, and [Wang and Li, 2019] adopt a hierarchical attention mechanism. Both models can benefit from HID. Additionally, [Zhang et al., 2017] capture hierarchical communitylevel information diffusion, but as a probabilistic model. Multiscale representation learning for graphs, in contrast, has recently received substantial attention [Yang et al., 2017; Shen and Chung, 2017; Sang et al., 2019; Morris et al., 2019; Chen et al., 2018; Perozzi et al., 2017]. Though closely related, we show that multiscale graph representation techniques fail to tackle information diffusion in Sec. 5.1.

3 Method

3.1 Notations and Definitions

An online social network (OSN) can be described as a platform that permits its users to share information [Guille et al., 2013]. Formally, the set of users that an OSN has is denoted as V. A corpus D is a set of diffusion paths, typically extracted from an OSN and generated by its |V| users during the information-sharing process. Our predictive task is information diffusion.

Definition 1. (DIFFUSION PATH): A sequence of non-repetitive users who have shared a certain information unit, denoting the ordered user path capturing the order in which the users of the OSN adopted the piece of information.

Definition 2. (INFORMATION DIFFUSION): Given |V| users and a corpus Dtrain , the task aims to complete the diffusion paths in the corpus Dtest with users in V. The first user (i.e., source user) of each diffusion path in Dtest is known.

Popular deep learning-based approaches commonly model information diffusion with user representation learning. We define a user representation as a mapping Φ : v ∈ V ↦→ Rd , which maps every user to a d-dimensional vector in the Euclidean space (d ≪ |V|). In practice, Φ is a |V| × d matrix estimated from a training corpus.

Algorithm 1 HID(s, p, d, Dtrain, F)

Input:

the number of coarse scales s

the coarsening rate between adjacent two scales p

the user embedding dimensionality d

an arbitrary information diffusion algorithm that leverages user representations F

a corpus Dtrain with user set V

Output: latent representation of users Φ : v ∈ V ↦→ Rd

• 1: D0 ←Dtrain
• 2: D1, D2, . . . , Ds ← UPSCALING(s, p, D0)
• 3: Initialize Φs
• 4: Φs ← INFDIFF(Φs,Ds, d,F)
• 5: for i = s -1 to 0 do
• 6: Φi ← DOWNSCALING(Φi+1,Di,Di+1)
• 7: Φi ← INFDIFF(Φi,Di, d,F)
• 8: end for
• 9: Φ←Φ0
• 10: return Φ

3.2 ProblemFormulation

We desire to learn Φ, a latent representation of users, to better predict information diffusion. Current approaches for estimating Φ suffer from two main disadvantages: (1) the multiscale property is not considered, and (2) their stochastic optimization can easily fall into local minima due to troublesome initial configurations. In light of these deficiencies, we introduce hierarchical user representation learning for modelling information diffusion in an OSN:

Given the number of coarse scales s, simplify the corpus Dtrain to a series of successively coarser corpora, D1, D2, . . . , Ds, with respective user sets V1, V2, . . . , Vs (|V| > |V1| > · · · > |Vs|). Learn the corresponding family of user representations Φ1, Φ2, . . . , Φs and then obtain the finest-granularity user representation Φ to predict the diffusion paths in Dtest.

3.3 Proposed Approach

Algorithm 1 outlines the overall HID approach. Our underlying method is general and can be applied to any technique for information diffusion that leverages user representations. We denote the information diffusion algorithm that can benefit from HID as INFDIFF. The INFDIFF procedure will learn user representations and predict information diffusion.

Upscaling. We present UPSCALING in Algorithm 2. The upscaling process achieves a successive abstraction over the users. Abstraction is done such that the coarser scale will have fewer users, but the key characteristics of the diffusion paths are mostly retained. Specifically, the change in diffusion paths is minimized and the user ordering is preserved.

Consider a corpus Dtrain of an OSN represented as a diffusion graph G = (V, E), where each node is a user in V and there is a directed edge pointing from node i to node j for every ordered successive user pair (user i, user j) in the corpus Dtrain. Accordingly, each diffusion path can be viewed as a path in this diffusion graph G.

Recall that [Qiu et al., 2018; Perozzi et al., 2017] have shown that popular graph embedding approaches are implicitly factoring a matrix containing entries of A1 , A2 , . . . , Ak , where k is the window size over the random walk, and the entry Akij is the number of paths between nodes i and j of length k. We define matrix ˜Am,k , a |V|×|V| matrix, for each diffusion path, representing the adjacency matrix of diffusion path m with step size k. Entry ˜Am,k ij is the number of times that the ordered pair of user i and user j with step k appeared in the diffusion path m, and thus can only be 1 or 0.

In this paper, the multiscale property serves the following functions: (1) capturing directed as well as both local and long-distance information adoption proximity between two different users, and (2) the consideration of distinct connections of information adoption patterns in terms of different transitional orders and diffusion paths. To capture the multiscale property of a corpus Dtrain, we define the following k-order diffusion proximity matrix:

where |Dtrain| is the total number of diffusion paths in Dtrain and l is the maximum possible step size in Dtrain (i.e., the length of the longest diffusion path minus one). The step of calculating A is called ObtainProximity. A accounts for the bi-directional co-occurrence patterns of users along diffusion paths, and may be decomposed or transformed, with subcomponents having a genuine practical interpretation, e.g.,

where τ is a pre-defined neighborhood threshold (τ < l) and thus An considers neighboring patterns in terms of similar information adoption time of users. Further,

where em is the source user's index in Φ of diffusion path m, and iem is a |V|-dimensional vector, which serves as an indicator function (having a 1 in the em-th entry and 0s elsewhere). In this manner, Ao considers patterns of whether a user would diffuse information originating from another user.

UPSCALING groups users to form hyper-users via clustering. UPSCALING operates in a bottom-up manner across all scales, and at each scale, users who have similar adoption patterns would form a hyper-user. Based upon A at scale i, we apply UpscalingOperator to form hyper-users at scale i+1. Possible upscaling operators include Hierarchical Agglomerative Clustering (HAC), Spectral Clustering, K-means, etc. The number of users at scale i + 1 is defined by p, i.e., the coarsening rate between adjacent two scales, and is calculated as the number of users at scale i divided by p.

The RewriteCorpus procedure then updates the corpus Di and obtains Di+1 by replacing user ID at scale i with the corresponding hyper-user ID at scale i + 1, while ensuring the resulting diffusion path is still valid. Since we want to make sure the change in diffusion paths is minimized and Algorithm 2 UPSCALING(s, p, Dtrain)

Input:

the number of coarse scales s

the coarsening rate between adjacent two scales p

a corpus Dtrain with user set V

Output: a series of successively coarser corpora, D1, D2, . . . , Ds

• 1: D0 ←Dtrain
• 2: for i = 0 to s -1 do
• 3: Ai ←ObtainProximity(Di)
• 4: Vi+1 ←UpscalingOperator(Ai,Vi, p)
• 5: Di+1 ←RewriteCorpus(Di,Vi,Vi+1)
• 6: end for
• 7: return D1, D2, . . . , Ds

the user ordering is preserved, we only consider the first occurrence of every hyper-user. In addition, if the number of users on a coarsened diffusion path is less than 3, we discard that diffusion path, because many diffusion models require at least 3 users on a diffusion path [Bourigault et al., 2014; Gao et al., 2017]. Corpora D1, D2, . . . , Ds is thus obtained. Downscaling. The DOWNSCALING process maps a coarser user representation Φi+1 at scale i+1 to its subsequent finergrained user representation Φi at scale i, which is used as the initialization point for learning the finer-grained user representation. Specifically, for each user at scale i, DOWNSCALING finds the user's corresponding hyper-user at scale i + 1, then assigns the learned hyper-user's representation (returned by INFDIFF) as that user's initial representation. DOWNSCALING transfers the knowledge of user representations across scales, and thus provides good initializations for learning, effectively avoiding troublesome configurations that are more prone to local minima in non-convex optimization [Chen et al., 2018].

4 Experimental Setup

We apply HID to current deep learning-based information diffusion models that involve user representation learning. For each, we compare accuracy and efficiency changes, with and without applying HID. In addition, HARP and Walklets are multiscale graph representation techniques to compare the multiscale representation learning aspect.

4.1 Baseline Methods

CDK [Bourigault et al., 2014] induces user embeddings such that users contaminated earlier are closer to the source user than users contaminated later or not contaminated.

CSDK [Bourigault et al., 2014] generates user embeddings such that users contaminated first are closer to the source user after applying the information embedding as an offset, than users contaminated later, or not contaminated at all.

Forest [Yang et al., 2019] is a deep diffusion model based on reinforcement learning (RL). RL incorporates the diffusion size information into the recurrent neural network model.

HARP [Chen et al., 2018] is a method for learning node embeddings of a graph by compressing the input graph prior to embedding it. HARP is a meta-strategy, proven to improve the state-of-the-art algorithms for embedding graphs.

Walklets [Perozzi et al., 2017] is an approach for learning multiscale representations of nodes in a graph, by subsampling short randomwalks (i.e., "skipping" over steps).

4.2 Datasets

Three real datasets are used. Table 1 gives the statistics.

Memetracker [Leskovec et al., 2009]. This corpus contains blog posts and Web news article from August 1, 2008 to April 30, 2009, and is often used for research on information diffusion [Bao et al., 2016]. Each website or blog is considered as a user. We consider a subset with roughly one thousand of most active users. Such filtering is common for fast verification of model performance [Wang et al., 2019].

Twitter [Yang and Leskovec, 2011]. This dataset retrieves Twitter tweets from June 1, 2009 to December 31, 2009. For each tweet, author, time, and content (i.e., information) are available. We consider users with at least 600 tweets and then discard diffusion paths with fewer than 10 users.

Digg [Hogg and Lerman, 2012]. This dataset contains stories promoted to Digg's front page over a period of a month in 2009. For each story, all Digg users who have voted for the story up to the time of data collection are captured. We consider the 500 most active users.

4.3 EvaluationMetrics

For each dataset, the set of diffusion paths is randomly split into two parts: 80% for training and validation (Dtrain), and the remainder for testing (Dtest). We evaluate the performance through the widely adopted metric Mean Average Precision (MAP) 2 [Bourigault et al., 2014; Bourigault et al., 2016; Wang and Li, 2019], computed as

where t is a diffusion path in Dtest, and P@k is the precision at rank k, i.e., the percentage of infected users among the top k users. isInfected(k) is 1 when the k-th user truly participates in this diffusion path, and 0 otherwise.

4.4 Parameter Settings

The hyper-parameters are chosen based on validation performance. For CDK, the maximum training epoch was 8, 000 and per epoch the number of samples was 5, 000. The initial learning rate was 0.01 with a decay of 1 × 10-6 . CSDK shared the same parameters, except 10, 000 for the number of samples per epoch and 1×10-12 for decay. For Forest, HARP, and Walklets, we used the parameters suggested by the authors. Forest used a maximum training epoch of 24. We built the diffusion graph (Sec. 3) for HARP and Walklets. Since the friendship network of Digg is available, we also tried the friendship network, reporting whichever gave better results (diffusion graph for HARP and friendship network for Walklets). We used the HARP algorithm type that gave the best performance. Specifically, HARP(node2vec) for Memetracker, HARP(LINE) for Twitter and HARP(DeepWalk) for Digg. Using HARP and Walklets, during the prediction, we rank the source user's neighbors according to the Euclidean distance in the user representation space (same technique introduced in CDK). To ensure a fair comparison, we reduced the number of training epochs for the HID enhanced version, according to the parameter s. Specifically, if the maximum training epoch of the baseline is e, the HID enhanced version uses e/(s + 1). The same set of the above hyper-parameters was used for all datasets. The user representation dimensionality was 64. HID requires two hyper-parameters, s and p. For results in Table 2, different values of s in {1, 2, 3} and different values of p in {1.2, 1.5, 2, 3, 4} were tried with a grid search using the validation data before choosing the bestperforming settings, which in general vary across datasets, baseline techniques, and the upscaling operators. How these two hyper-parameters affect HID is discussed in Sec. 5.2.

2 Additional metrics such as Area Under the Receiver Operating Characteristic Curve were computed, but we opted not to report due to the similar trend that all metrics indicate and limited space.

5 Evaluation 5.1 Results

We present the results in Table 2. HID consistently produces better results than all compared methods. On Memetracker, the relative gains of HID over CDK, CSDK, and Forest are 6.1%, 4.34%, and 4.72%, respectively. On Twitter, the baselines tend to perform very well with high MAP scores (e.g., CDK has a MAP score of 0.5763). Still, HID is able to bring performance gains. On Twitter, the improvements introduced by HID(CDK), HID(CSDK), and HID(Forest) are 3.61%, 2.47%, and 2.16%. Given the long diffusion paths of Digg (see Table 1), upscaling succeeds at preserving the characteristics of the original corpus (Fig. 2), which provides more opportunities for HID to be effective. The gains are particularly striking on Digg: HID(CDK), HID(CSDK), and HID(Forest) outperform the baselines by 14.75%, 3.28%, and 12.6%, respectively. The somewhat more modest gain of HID(CSDK) on Digg might stem from the additional learning of information representations, which plays a dominant role in CSDK's diffusion modeling process. The improvements introduced by HID are statistically significant: every experiment is repeated 5 times to ensure the reliability of our results, and we consistently see higher accuracy with our framework.

In Table 2, results on different upscaling operators are also demonstrated. In most cases, HAC yields the best results, and occasionally, is significantly better than K-means and Spectral Clustering (e.g., on Digg). This might be because HID operates in a hierarchical way, which accords with HAC. Spectral Clustering tends to give the lowest performance gains. Spectral clustering treats the data points as vertices of a graph, and connects vertices that are close enough. Noisy online data without well-separated connected components might be the reason why Spectral Clustering is less suitable.

We also compare HID with HARP and Walklets in Table 2. HARP and Walklets are multiscale graph representation learning techniques. Between the two, HARP gives the better results. However, suffering from the closed-world assumption [Guille et al., 2013], neither of them are able to effectively tackle the prediction task of information diffusion. On the 3 datasets, HARP and Walklets give worse or only comparable results to CDK, CSDK, and Forest, which are algorithms designed for information diffusion and avoid the need of a pre-defined graph. Approaches requiring a predefined graph are said to be limited in terms of their ability to explain future diffusion and are less optimal [Bourigault et al., 2014; Gao et al., 2017]. Based upon the above, HID, a framework for enhancing information diffusion techniques, gives superior performance compared to HARP and Walklets.

5.2 Parameter Sensitivity

HID involves 2 parameters: the number of coarse scales s and the coarsening rate p. Using CDK as the baseline with HAC, we examine how different choices of s and p affect the extent of coarsening on the original corpus and HID performance.

We show the effect on the original corpus in Fig. 2 (a). The first column reports the effect on the relative total number of users and diffusion paths, i.e., the ratio of the number of users/diffusion paths of the coarsened scale to that of the original corpus, with varied values of s when p = 2; and the second column shows the same but with varied values of p when s = 1. The first 3 scales tend to affect the corpus the most. Fewer than 10% of users remain after 4 scales when p = 2, and approximately only 20% remain when p is greater than 5 with s = 1, both indicating the critical point that might suffer from performance loss. The level of coarsening varies across datasets, which implies the level of difficulty for HID to bring improvements. Among the 3 datasets, s and p tend to affect Twitter the most, which explains why improvements on Twitter are relatively hard to achieve (Sec. 5.1).

We measure HID performance on the testing set as a function of s and of p in Fig. 2 (b). With regard to s, the performance of HID first improves as s increases, then decreases as s keeps increasing. The performance is expected to increase when coarsening is appropriate. In HID, the coarsening operates over the users. The coarse scale learns initial user representations for the finer scales, so a suitable extent of coarsening with an adequate coarsening strategy will ensure the characteristics of users' behavior are preserved in the coarsened scales. When s becomes too large, the number of users and diffusion paths remaining in the coarsest scale will be too small to serve as a summary of the original corpus. This is why the performance would decrease afterwards, which is not surprising. Similarly, we observe that there is a range of acceptable values for p, after which p becomes too large and destroys the original patterns that are crucial for information diffusion prediction. Both parameters have a fairly high impact on the performance. The range of best s (or p) can be implied by Fig. 2 (a). E.g., on Memetracker, the critical point for s to affect the original corpus is around 4, hence, as shown in Fig. 2 (b), the range of best s is from 1 to 4. Practitioners can use Fig. 2 (a) to facilitate the selection of s and p.

5.3 Scalability

In Fig. 3, we compare the run time of HID and other techniques. All models run on a single machine with 256 GB memory, 48 CPU cores at 2.30GHz, and an NVIDIA Quadro K6000 graphics card. Though sharing the same total number of training epochs, HID is always more efficient compared to the baseline, and becomes more efficient as s increases. This is because fewer users and activities are involved at the coarsened scales. The run time decreases almost linearly with respect to the remaining corpus size. A trade-off between efficiency and performance is sometimes observed when s > 1 (e.g., Twitter). Still, HID can be a valuable tool for large-scale online networks due to its substantial scalability.

6 Conclusion

This paper presents a novel hierarchical framework for the task of information diffusion. The proposed framework HID can be layered on top of all information diffusion techniques that leverage user representations. HID facilitates more efficient learning and accurate prediction. Extensive experiments show the superior performance. In the future, we hope to extend HID to model additional aspects (e.g., information representations, combination of different upscaling operators, mix of knowledge by downscaling) so as to obtain even further improvements.

Acknowledgements

This research was supported in part by NSF IIS-1703883 and NSF S&AS-1723869.