Pedro Ramaciotti Morales

Lionel Tabourier

Raphaël Fournier-S'niehotta

Testing the Impact of Semantics and Structure on Recommendation Accuracy and Diversity

The Heterogeneous Information Network (HIN) formalism is very flexible and enables complex recommendations models. We evaluate the effect of different parts of a HIN on the accuracy and the diversity of recommendations, then investigate if these effects are only due to the semantic content encoded in the network. We use recently-proposed diversity measures which are based on the network structure and better suited to the HIN formalism. Finally, we randomly shuffle the edges of some parts of the HIN, to empty the network from its semantic content, while leaving its structure relatively unaffected. We show that the semantic content encoded in the network data has a limited importance for the performance of a recommender system and that structure is crucial.

Introduction

A Recommender System (RS) helps users in selecting items from large sets when their size makes individual consideration impractical or even impossible [START_REF] Ricci | Recommender systems handbook[END_REF]. To propose relevant recommendations to users, a RS may process previous choices made by users, item/user meta-data, and contextual information. Initially, the performances of RS were measured with the so-called utility or accuracy metrics [START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF], which evaluate, for example, the error committed when predicting the rating a user would give to a specific item. Later, other properties of recommendations beyond accuracy were suggested, because users also wish for surprising recommendations and thus should be proposed diverse items [START_REF] Sean M Mcnee | Being accurate is not enough: how accuracy metrics have hurt recommender systems[END_REF]. Moreover, diversifying recommendations is also desirable to guarantee that people are not shut in a small subset of homogeneous recommendations, a phenomenon known as a filter bubble [START_REF] Pariser | The filter bubble: How the new personalized web is changing what we read and how we think[END_REF].

RS models are often separated between content-based filtering and collaborative filtering approaches. Many recent RS tend to use hybrid methods that mix both approaches [START_REF] Burke | Hybrid recommender systems: Survey and experiments[END_REF]. Among these, methods relying on the Heterogeneous Information Network (HIN) framework are gaining popularity [START_REF] Sun | Pathsim: Meta path-based top-k similarity search in heterogeneous information networks[END_REF]. HINs are graphbased representations with different types of node: some represent users, others represent items, and a new type of node (or layer) is added for each kind of information in the system [START_REF] Burke | Hybrid recommendation in heterogeneous networks[END_REF]. Then nodes of different types are connected with links representing a specific type of relation, such as a user selected an item, or an item belongs to a given genre, etc. A simple example consists in readers linked to books they read, which are in turn linked to genres (categories).

In this work, we want to evaluate how different parts of a HIN impact the diversity and the accuracy of the recommendations a RS based on this HIN may produce. Using a RS derived from Pathsim [START_REF] Sun | Pathsim: Meta path-based top-k similarity search in heterogeneous information networks[END_REF], which relies on random walks on HINs, we may gradually include different parts of the HIN into the RS in a controlled way. These different parts encode different meta-data on users and items: some nodes may represent the demographic group of users (say, their gender), others may represent a category of items (e.g., drama or comedy for movies), etc. Most current diversity measures may not benefit from the full structural information of networks, since they are defined only with the output of the recommendation process (the lists of recommended items and their features) [START_REF] Kunaver | Diversity in recommender systems-a survey[END_REF][START_REF] Silveira | How good your recommender system is? a survey on evaluations in recommendation[END_REF]. Thus, our evaluation of diversity relies on a framework especially suited to HINs [START_REF] Ramaciotti-Morales | Measuring diversity in heterogeneous information networks[END_REF].

Another important goal of our work is to measure whether the performance of a HIN-based RS is mostly due to the nature of the semantic information encoded, or to a structural shortcut effect. A HIN representation may contain connections between items or users who may not share a lot of common features. For instance, two users might have different tastes while living in the same city and a HIN representation would connects them through their zip code. A HIN-based RS would use these "shortcuts" to recommend items otherwise unreachable, affecting diversity. We address this problem of balance between structural and semantic information by using a configuration model [START_REF] Newman | The configuration model[END_REF] of our HIN. Randomly shuffling edges in a given part of the HIN (while keeping the degree distribution unaffected), we separate the effects of those semantic and structural information.

To summarize, the research questions addressed are: Q1: How to test the effect of different parts of a HIN on the accuracy and the diversity of recommendations?, and Q2: Are the effects of different parts of a HIN on accuracy and diversity due to the semantic content encoded in them?

This article is structured as follows. In Section 2, we discuss the related work. In Section 3, we provide the definitions of concepts used in this paper, in particular the formal definition of a HIN and suited diversity measures. We also expose the design of our HIN-based RS model. In Section 4, we detail a series of experiments which correspond to one of our contributions:

1. we provide the first application of network diversity measures to recommendations computed on HINs (Sec. 4.1).

2. we use a simple, well-known procedure to compute recommendations on HINs [START_REF] Sun | Pathsim: Meta path-based top-k similarity search in heterogeneous information networks[END_REF], and test it on the datasets to answer question Q1. We show that depending on the information included, such a method can yield accurate and diverse recommendations (Sec. 4.2).

3. finally, we use edge shuffling of some parts of a HIN to show that it is not always possible to explain the performance of recommendations by the semantic information encoded in HINs, thus answering question Q2 (Sec. 4.3). To the best of our knowledge, this is the first work to investigate how the global structure of a HIN affects accuracy and diversity of recommendations.

Related Work

HIN-based RSs are rapidly developing into a subdomain of information filtering and recommendation [START_REF] Burke | Hybrid recommendation in heterogeneous networks[END_REF][START_REF] Shi | A survey of heterogeneous information network analysis[END_REF]. HINs enable mixing past choices of users with semantic information about items and users in a unified graph-based representation. In a HIN, if a set of users are linked to books they have chosen, and these books linked to genres, for example, a HIN-based RS may exploit the collective choices made by users (the set of links representing choice), and the genres of books chosen by users. Recommendations based on content (recommending books of previously chosen genre), but also on collective choice (recommending books chosen by users that have similar taste) are then possible. The HIN formalism has been shown to perform well and to improve interpretability [START_REF] Shi | Heterogeneous information network embedding for recommendation[END_REF][START_REF] Shi | Semantic path based personalized recommendation on weighted heterogeneous information networks[END_REF]. Moreover, HINs can deal with cross-domain recommendation, often useful in cold-start situations [START_REF] Tang | Cross-domain collaboration recommendation[END_REF], and can exploit social relations between users [START_REF] Yang | Circle-based recommendation in online social networks[END_REF]. They also allow predictions based on implicit feedback [START_REF] Yu | Personalized entity recommendation: A heterogeneous information network approach[END_REF]. RS evaluation usually focuses on accuracy: measuring the error on predicted ratings with metrics such as RMSE or MAE, or measuring the error committed on items selected by users using metrics such as precision, recall, or F1-score. However, almost two decades ago, it was acknowledged that properties beyond accuracy play an important role in user satisfaction [START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF][START_REF] Sean M Mcnee | Being accurate is not enough: how accuracy metrics have hurt recommender systems[END_REF]. These properties aim at grasping how novel or surprising a recommendation is [START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF] or how diverse the proposed recommendation list is [START_REF] Ziegler | Improving recommendation lists through topic diversification[END_REF].There is little consensus on the naming of these desirable properties, but they may be collectively referred to as diversity measures, indicating a degree of (dis-)similarity between recommended items. Some authors consider two items similar if they are chosen by the same users [START_REF] Hurley | Novelty and diversity in top-n recommendationanalysis and evaluation[END_REF][START_REF] Zhang | Novelty and redundancy detection in adaptive filtering[END_REF], while others consider items similar if they are of the same type [START_REF] Ziegler | Improving recommendation lists through topic diversification[END_REF]. These notions are often called novelty or intra-list similarity . Some works focus on the improbability, or the surprisal, of a recommendation considering the users' past choices, while others focus on personalization, i.e., the degree to which recommendations are different from one user to another [START_REF] Zhou | Solving the apparent diversity-accuracy dilemma of recommender systems[END_REF]. Measuring diversity is also important for specific applications, such as detecting context changes [START_REF] Amaury | The new challenges when modeling context through diversity over time in recommender systems[END_REF] or measuring phenomena related to diversity loss, such as filter bubbles and echo chambers [START_REF] Pariser | The filter bubble: How the new personalized web is changing what we read and how we think[END_REF].An extensive survey recently compiled diversity measures for RS [START_REF] Kunaver | Diversity in recommender systems-a survey[END_REF].

In information filtering, searches in graphs sometimes call to some notion of diversity on node rankings (i.e., item rankings) [START_REF] Li | Scalable diversified ranking on large graphs[END_REF][START_REF] Tong | Diversified ranking on large graphs: an optimization viewpoint[END_REF]. While many studies consider diversity with respect to some node labeling, few exploit the variety of paths formed by relations between nodes of different types [START_REF] Kunaver | Diversity in recommender systems-a survey[END_REF]. Dubey et al. [START_REF] Dubey | Diversity in ranking via resistive graph centers[END_REF] use, as we do in this article, the notion of random walk along these paths, which are usually called meta-paths in HINs. Furthermore, some works use the notion of random walk in relation to diversity [START_REF] Jiang | Degenerate feedback loops in recommender systems[END_REF][START_REF] Nandanwar | Fusing diversity in recommendations in heterogeneous information networks[END_REF], although not as a measure to evaluate resulting recommendations of RSs in HINs. While there are theoretical propositions of diversity measures adapted to HIN [START_REF] Ramaciotti-Morales | Measuring diversity in heterogeneous information networks[END_REF], there are no available experiments that illustrate their applicability.

Heterogeneous Information Networks and Diversity

In this section we give definitions and notations about HINs that are used in the rest of this paper. By combining these definitions with random walks on graphs, we are able to define the diversity measures that are then exploited in Section 4.

Heterogeneous Information Networks

Definition 1 (Heterogeneous Information Network [START_REF] Shi | Heterogeneous information network analysis and applications[END_REF]). A Heterogeneous Information Network (HIN) H = (G, A, R, ϕ, ψ) is a directed graph G = (V, E) with mapping functions ϕ : V → A and ψ : E → R, where A and R are respectively node and edge label sets.

Slightly simplifying notations, we refer to a group of nodes or edges by its label. Edge labels in R represent relations between entities of different object groups in A.

Definition 2 (Heterogeneous Information Network Schema [START_REF] Shi | Heterogeneous information network analysis and applications[END_REF]). The network schema of a HIN H = (G, A, R, ϕ, ψ) is a directed graph, the nodes of which are the types A, and the edges are the relations of R.

A HIN schema (or simply schema) is a graphical and summarized representation of a HIN, which shows the groups of nodes and links.Figure 1 Definition 4 (Meta-path [START_REF] Shi | Heterogeneous information network analysis and applications[END_REF]). A meta-path of a HIN is a path on its schema, and it is denoted by

Π = A 1 R 1 -→ A 2 R 2 -→ ... R l -→ A l+1 , or more simply by Π = R 1 R 2 • • • R l .
In the example of Figure 1, Π = R rates R T y is a meta-path connecting users to the types of items that they have rated.

Random Walks and Meta-Path Diversities on HINs

Given a HIN H = (G, A, R, ϕ, ψ) let us consider a random walk along a metapath Π starting in S ∈ A and ending in T ∈ A. Let us also consider the random variable X, the node of T where the random walk along Π ends. We are interested in the probability mass function (PMF) over the nodes of T , denoting p Π the PMF P (X = t ∈ T ) when the walk started randomly at any node of S. Similarly, let us denote by p Π (s) the PMF P (X = t ∈ T |s ∈ S), when the walk started at the node s ∈ S. To illustrate this better, let us consider a HIN with 2 users rating 3 items classified in 2 types, corresponding to the schema in Figure 1. In Figure 2, we illustrate the computation of PMFs for such random walks on the simple example presented in Figure 1, following the meta-path Π = R rates R T y : p Π when starting randomly in a set of users U = {u 1 , u 2 }, and p Π (u 2 ) when starting from user u 2 . Different diversity measures can then be computed from these PMFs (e.g., Shannon entropy, Gini coefficient). We use perplexity, denoted by P and computed for a PMF p as

HIN

U R rates u 1 u 2 I i 1 i 2 i 3 Ty R Ty t 1 t 2 1/2 1/2 2/4 1/4 1/4 3/4 1/4 p Π = (3/4, 1/4) 1 1/2 0 1/2 1/2 1/2 p Π (u 2 ) = (1/2, 1/2)
P(p) = 2 E(p) , with E(p) = -|T | i=1 p i log 2 (p i ), where E(p)
is the Shannon entropy of the PMF. We select perplexity because of its intuitive interpretation: it measures the degree of unexpectedness of a random variable. Perplexity accounts for variety (number of possibilities available) and balance (how probability is distributed among those possibilities) [START_REF] Stirling | A general framework for analysing diversity in science, technology and society[END_REF]. Interestingly, the perplexity of a PMF p = (p 1 , p 2 , . . .) can be interpreted as the number of elements of a uniform PMF that has the same Shannon entropy as p. For instance, p = 1 3 , 1 3 , 1 3 has perplexity P(p) = 3 (i.e., uniform over 3 elements) while p = 6 10 , 2 10 , 1 10 , 1 10 has perplexity P(p ) = 2.97, i.e., p has the same entropy as a uniform distribution over 2.97 elements. So p is a distribution over four possibilities, but has lower diversity than p.

Using these notions, and following [START_REF] Ramaciotti-Morales | Measuring diversity in heterogeneous information networks[END_REF], we define the two following diversity measures for a meta-path Π of a HIN H:

Mean Individual diversity: P MI (Π) = s∈S P(p Π (s)) 1/|S| , Collective diversity: P Col (Π) = P(p Π ),
with P being the perplexity.

The Mean Individual (MI) diversity along a meta-path Π is the geometric mean of the perplexities of the PMFs corresponding to random walks starting on each element s ∈ S and ending in T . It can thus be interpreted as the diversity in terms of elements of T available on average for one element of S. Collective (Col) Diversity along meta-path Π is the perplexity of the PMF corresponding to a single random walk starting randomly on an element s ∈ S and ending in T . It may be interpreted as the diversity in terms of elements of T available to the entire group of elements of S. In the example of Figure 2, the collective diversity of types available to users is P Col (Π) = P(3/4, 1/4) = 1.7547, and the mean individual diversity is

P MI (Π) = (P (1, 0) p Π (u 1 ) • P (1/2, 1/2) p Π (u 2 ) ) 1 2 = (1 • 2) 1 2 = √ 2.

Recommendations as Processes on HINs

A recommendation process consists in proposing items to a user that he or she has not selected before. In a HIN framework, it amounts to creating new edges:

Definition 5 (Recommendation on a HIN). A recommendation process on a HIN H = (G, A, R, ϕ, ψ) is a process F (H) that produces a new collection of edges

F : H → E rec ∈ V × V .
The edge set E rec is composed of links between users and their recommended items.

A HIN can then be updated with a new relation R rec such that ψ(e) = R rec for e ∈ E rec , so that recommended edges can be used in meta-paths. In the following section, we are interested in including recommendation edges in meta-paths to measure the diversity related to these paths, as described in Subsection 3.2. We may then measure how diverse the recommendation process is.

A HIN Graph Spreading Recommender System

In order to produce recommendations that can include different parts of a HIN in a controlled and interpretable fashion, we consider a recommendation procedure well-known to the RS community (cf. [START_REF] Sun | Pathsim: Meta path-based top-k similarity search in heterogeneous information networks[END_REF]). This method belongs to a larger family of RS based on random walks (e.g., [START_REF] Jiang | Degenerate feedback loops in recommender systems[END_REF][START_REF] Nandanwar | Fusing diversity in recommendations in heterogeneous information networks[END_REF]).

Precisely, it consists in computing the probability produced by random walks along a meta-path, starting on a single user and ending on the set of items. Then, we simply recommend the items with the highest probability that have not been previously chosen. This allows us to measure the effect of different parts of a HIN in an interpretable way. Indeed, we can consider different meta-paths that include different meta-data (e.g., book genre, user location), and produce different probabilities that can be added with different coefficients to modulate their relative importance in recommendations. For instance, we may give a high weight to the meta-path related to demographic information about the users and a light weight to information related to items typologies, or vice versa. Let us formalize this type of recommendation by considering K different meta-paths Π k (with k = 1, . . . , K) starting on S ∈ A and ending in T ∈ A. Let us consider the parameters α 1 , . . . , α K , such that α k = 1 and 0 ≤ α k ≤ 1. For every element s ∈ S (typically the user group), we compute a score S as a PMF over T (typically the item group):

S(t|s) = K k=1 α k p Π k (s), for t ∈ T. (1)
Using the score S(t|s) we recommend the top ranking elements of T for s ∈ S (among those not already selected). This RS shares some principles with the one detailed by Zhou et al. [START_REF] Zhou | Solving the apparent diversity-accuracy dilemma of recommender systems[END_REF], in which mass (called resource in [START_REF] Zhou | Solving the apparent diversity-accuracy dilemma of recommender systems[END_REF]) is assigned to items and then distributed through edges to find relevant items according to the final resource distribution.

It should be noticed that this RS is not new and our point is not to argue that it performs better than other methods. However, we show in the next section that its accuracy is comparable to that of popular methods. Its main interest here is that it allows us to include different parts of a HIN in the recommendation process to measure separately the effects on accuracy and diversity of these parts.

Experiments

Here we present the data used, the protocols for our experiments1 , and their results to answer our research questions.

Datasets and Meta-Path Diversities of HIN

We use two datasets in our experiments, the well-documented MovieLens 100K dataset (ML100K) [START_REF] Harper | The movielens datasets: History and context[END_REF] and the Douban Movie (DM) dataset [START_REF] Zafarani | Social computing data repository at ASU[END_REF]. The latter has been used in HIN-based RS studies, as it presents a rich HIN structure [START_REF] Shi | Semantic path based personalized recommendation on weighted heterogeneous information networks[END_REF]. We detail in Figure 3 the characteristics of these datasets: groups of entities, their sizes, and the relations that join them. We also show the corresponding HIN schemas with their object groups and link groups (relations). Both datasets contain information on the rating (from 1 to 5) given to films by users, and the fact that a user has rated a movie is represented by the relation R rating . We consider that a user likes a film if he or she rated it 3 or more (for both datasets), and we refer to the corresponding relation as R likes . Figure 3 Now, we can illustrate the use of the diversity measures on HINs defined in Section 3 with the ML100K and DM datasets. While diversity measures from the literature essentially rely on how proposed or selected items are distributed into types, the diversity measures described in Section 3.2 allow to consider a larger spectrum of diversity notions. Let us consider the example of a diversity computed on meta-path Π 1 = R rec R Ty . It is the diversity of types of movies in a recommendation list, consequently it captures the same intuition as the Intra-List Similarity does in [START_REF] Ziegler | Improving recommendation lists through topic diversification[END_REF]. However, the meta-path based diversity allows us to express other forms of diversities. For instance, the meta-path

Π 2 = R rec R -1
likes R likes R Ty relates to the diversity of types of movies liked by users who also liked movies that they were recommended.

In Figure 4, we report experimental diversity measures on both datasets. We consider meta-paths of length 3 starting in S and ending in T (with S, T ∈ A), which are node groups containing semantic information about users and items respectively, so

Π = R -1 S R X R T .
Here X stands for rating, liked or recommended. Then, we compute the Mean Individual diversity on these paths: P MI (Π). Regarding the recommendation links, we use two standard RSs in these experiments, each recommending a list of 5 items to the users: User-Based Collaborative Filtering (UBCF) and Implicit Pure Popularity (IPP), IPP recommends to the users the top-5 most liked movies, not already rated by the user. The figure reads as follows: it reports Mean Individual diversities for all combinations of node groups S and T and R X is either R likes , R rec (U BCF ) or R rec (IP P ). For instance, P MI (R -1

Lo R rec (U BCF )R Ty ) is the Mean Individual diversity of movie types recommended to users using UBCF, averaged over locations.

The measurements of these diversities provide insights about the structure of the HIN and about the RS. First, notice that most P MI (Π) using recommendations are lower than those using likes. This is only a consequence of the fact that recommended lists are of length 5, while the average user likes larger numbers of items in these datasets. Similarly, the fact that

P MI (R -1 S R X R Ac ) is much larger than P MI (R -1 S R X R Ty ) or P MI (R -1 S R X R Di )
on DM dataset reflects the fact that movies have more actors than directors or types/genres. Other phenomena are revealed by these diversity measures. For example, the diversity of release year of films by age groups (i.e., of R -1

Ag R likes R Ye ) in the ML100K dataset is low. This could point to the fact that users from a given age group tend to choose films from a narrow period of time, however testing this hypothesis falls outside the scope of this article. Note also that these diversity measures allow us to compare diversities from one RS to another. For example UBCF produces recommendations that are consistently less diverse than those produced using IPP on the ML100K dataset.

Effect of the HIN Structure on Accuracy and Diversity of Recommendations

Having established and illustrated the use of meta-path diversities, we now focus on the effect that the structure of HINs has on accuracy and diversity of recommendations. For this purpose, we use the RS described in Section 3.4. It allows us to include in the recommendation process different parts of a HIN in a controlled way. Moreover, its underlying mechanic, based on meta-path constrained random walks, is common to several techniques of HIN-based recommendation (e.g., [START_REF] Shi | Semantic path based personalized recommendation on weighted heterogeneous information networks[END_REF][START_REF] Sun | Pathsim: Meta path-based top-k similarity search in heterogeneous information networks[END_REF][START_REF] Yu | Recommendation in heterogeneous information networks with implicit user feedback[END_REF]). Note that our goal here is to explore the consequences on accuracy and diversity of integrating different parts of a HIN, rather than optimizing this RS to obtain the best possible performance. Many choices are available, as we can mix all kinds of meta-paths to produce a recommendation. However, we choose to consider a RS that mixes only two metapaths for each dataset: one denoted Π(X) which includes a user-content object group (e.g., the location of a user), and one Π(Y ) including an item-content object group (e.g., the genre of a movie). By tuning the balance between these two metapaths, we can control what kind of information is taken into account to produce a recommendation. Practically, Equation (1) here takes the form:

S(t|s) = (1 -α) p Π(X) (s) (t) + α p Π(Y ) (s) (t)
s ∈ U and t ∈ I and parameter α ∈ [0, 1] tunes the balance between Π(X) and Π(Y ). So, α = 1 means that only the item-content is used in computing recom-mendations and when α = 0 only the user-content is used. Precisely, the user-

content path Π(X) is R X R -1
X R likes where X stands for a user-content group, and the item-

content path Π(Y ) is R likes R Y R -1
Y where Y stands for an item-content group. Figure 5 illustrates the meta-paths selected on the HIN schema.

U I Y X User meta-data side Meta-path Π(X) Modulated by 1 -α Item meta-data side Meta-path Π(Y ) Modulated by α R likes R X R -1 X R Y R -1 Y Figure 5
: Schematic illustration of the recommendation procedure used in the experiments, where parameter α modulates two meta-paths, Π(X) and Π(Y ), containing user and item meta-data.

We use α ∈ {1.0, 0.8, 0.6, 0.4, 0.2, 0.0} to show the effect of gradually moving from recommendations purely based on item meta-data (α = 1) to recommendations based purely on user meta-data (α = 0). While there are several possible combinations of meta-paths (8 combinations for ML100K and 6 for DM), we only focus on a few of them (4 for each dataset) for ease of illustration and also because they suffice to show the effects that the HIN structure has on accuracy and diversity.

Accuracy

Figures 6a and6b show the F1-score of recommendations using the ML100K and DB datasets respectively. For each experiment, we set a list size (the number of items included in a recommendation list proposed to each user). For a given list size and α, a random 10% of user-item links are hidden. We compute the items recommended to users (corresponding to the edges R rec in Figure 3) with our HIN-based RS and compare it to the test set to evaluate the F1-score of our prediction. Each figure in the mosaic corresponds to a combination of meta-paths, with a given X and a given Y .

While it is not our main objective to characterize the performance of this recommendation method, is it worth noticing that it may produce relevant recommendations: some combinations of meta-paths and α result in F1-scores comparable to other RS in different settings (see, e.g., [START_REF] Hatami | Improving results and performance of collaborative filtering-based recommender systems using cuckoo optimization algorithm[END_REF][START_REF] Shi | Heterogeneous information network embedding for recommendation[END_REF]). Note also that whatever the list size, the pure item-content recommendation is never the highest F1-score. In other words, accuracy is, unsurprisingly, increased (up to a certain point) by the addition of user-content meta-data for both datasets. On Douban Movie with a fixed list size, the best F1-scores are obtained with a mixture of item-and user-related information. This is less true for ML100K, where user-related information seems often more valuable than item-related information. We also notice that the range of F1-score values varies significantly depending on the balance between meta-paths: we see variations by up to a factor of 14 on ML100K (list of size 15 using user locations and movie types). This observation is consistent with the idea that while some meta-data brings relatively irrelevant information for recommendation (e.g. movie year of release in ML100K), other are much more valuable for the accuracy of the recommendation (e.g. user location in ML100K).

Diversity

For the same recommendation protocol, we now measure the Mean Individual and Collective diversities of the recommendation lists, in terms of types of items recommended. In other words, we compute P MI (Π) and P Col (Π) with the Π = R rec R Ty meta-path. The results are displayed in Figures 7a and7b, following the same display organization as figures in 4.2.1. Figures 7a and7b highlight the interpretation associated with diversity measures based on meta-paths, and especially the contrast between Mean Individual diversity and Collective diversity. For both datasets, Mean Individual diversity monotonically increases with the list size, which is expected: more items recommended to a user implies that the user may access more types. In other words, variety increases with the list size (although not necessarily balance). However, this tendency is limited as perplexity cannot be larger than the available number of types (19 in ML100K, 36 in DM). While the Mean Individual diversity grows with the number of recommended items, Collective diversity may stagnate or even decrease. For instance, we can read on DM dataset that Collective diversity de-creases with the list size for all α > 0 when X = Gr (Groups of users) and Y = Ty (movie Types). This result is subtle but important in our opinion. It means that even if each user is individually recommended more diverse items, the whole group of users are recommended less diverse items.

Other trends can be isolated from these experiments, we report a few of them. First, we observe that including user meta-data tends to improve accuracy, but also diminishes Collective diversity. This is more obvious on ML100K dataset, where combinations which bring higher F1 scores, are often the ones which have the lowest diversities (both Collective and Mean Individual). Also, including more user meta-data usually has little effect on Mean Individual diversity. This observation is quite surprising as user meta-data can connect users of the HIN who potentially have very little in common (for example users of a same gender), so we would expect that these links give access to a large variety of items. We think that these observations are certainly related to the HIN structure and we begin to address this question in the next section.

Testing Semantic Relevance of Links Using the Configuration Model

The previous results raise some interesting questions. Why does the inclusion of certain meta-paths changes the accuracy and the diversity more than others? What is the property of user-content links that allows for more accurate recommendations? A natural assumption is that they contain relevant semantic information about the origin of the users' preferences.

To test this hypothesis, we propose an experiment inspired by the field of social network analysis (SNA). To identify the specificities of a real network in SNA, it is usual to compare its structure to a random graph model with a similar degree sequence, that is to say a graph in which nodes have the same number of connections as in the original graph, but distributed randomly. This model is often referred to as the configuration model [START_REF] Newman | The configuration model[END_REF]. A usual way to perform such a comparison consists in iteratively shuffling the links of the existing graph by exchanging their extremities. Here, we propose to follow this process for the edges of a specific relation (link group) of the HIN. To illustrate this idea, let's consider the example of the user-content links R Lo : by shuffling only those links, we do not modify the number of individuals per location. Thus we leave an essential property of the original HIN untouched, that is its degree sequence. However, we empty this part of the HIN of its semantic meaning, because the location associated to a user is now random.

As for the protocol itself, we proceed as follows: we focus on a recommendation based on the mixing of two meta-paths, one using user-based information and another using item-based information, as we did previously. We select the combinations that produced the most accurate recommendations: user location (Lo) and movie type (Ty) for ML100K, and user groups (Gr) and movie actors (Ac) for DM. In addition to the recommendation produced on the original ML100K HIN (respectively DM HIN), which was reported in Section 4.2, we make recommendations on several realizations of a HIN where R Lo (resp. R Gr ) have been randomly shuffled. Then we compare the accuracy, Mean Individual and Collective diversities obtained on the real HIN to the values on the randomized HINs. We better detail this procedure thereafter.

We produce 100 randomized versions of the HIN for the ML100K by shuffling the edges in the R Lo link group, and 20 randomized HIN for the DM dataset by shuffling the edges in the R Gr link group. Then, for each list size and for α ∈ {0.8, 0.6, 0.4, 0.2, 0.0}, we compute the 0.1-0.9 quantile range of the F1score, Mean Individual, and Collective diversities. Note that α = 1 produces recommendations using only item-related meta-paths and is of no interest as it does not include randomized parts. Lower α values imply that randomized links from R Lo (ML100K) or R Gr (DM) are used in the recommendation process. A value of α = 0 means that only the suffled link group R Lo (ML100K) or R Gr (DM) was used in computing recommendations. The resulting quantile ranges, compared to the values obtained with the original HIN from Section 4.2 are shown in Figure 8.

We observe in all cases that the recommendations on the original HIN and on its randomized versions are comparable in terms of accuracy and diversities. These results are counter-intuitive: it seems that emptying important parts of the HIN of its semantic content does not have a significant impact on the recommendation. These results are surprising as our recommendation process relies exclusively on the number of paths in the HIN connecting a user to an item. Our results are of course limited to the selected parameters and datasets used and call for further investigation in other contexts. Still, they tend to disprove the underlying hypothesis that the relevance of meta-path recommendations only comes from the semantic information that they contain. They could indicate that the number of connections of a node (which is not affected by the randomization) is the mostand even the only -important information in the recommendation process based on the HIN structure. This new hypothesis is not tested in this article as it demands a wider experimental setting than the one considered for the purposes stated in the

Conclusion

We used recently proposed diversity measures for the evaluation of recommendations on HINs. They are based on the perplexity of PMFs resulting from random walks along meta-paths over a Heterogeneous Information Network. While standard diversities measures usually focus on the distribution of the recommended items into types, we may measure diversity on an individual and collective level, revealing that these two approaches may lead to different conclusions. We illustrated the experimental uses of these measures with an existing RS and two well-known datasets. We then presented a method to explore the effects of including different meta-paths in the recommendation process, evaluated its accuracy, and analyzed recommendations produced by combining different meta-paths. We showed how including different parts of a HIN in a recommendation may significantly change accuracy and diversity. For both datasets, including meta-paths with user-content information improved accuracy but often reduced collective diversity.

Finally, we tested the influence of the semantic content on the accuracy and diversity of recommendations. We randomized part of the HIN structure to remove its semantic meaning, while keeping the degree sequence of the HIN untouched. Surprisingly, this random shuffling did not change significantly accuracy or diversity. While these results are limited to a restricted number of datasets and parameters, they indicate that the effects of the information encoded in the structure of a HIN on recommendations are not only due to their semantic meaning.

Figure 2 :

 2 Figure 2: Example of a HIN (left) having a schema as in Figure 1, with 2 users rating 3 items classified into 2 types, and computation of p Π (middle) and p Π (u 2 ) (right) for meta-path Π = R rates R T y .

Figure 3 :

 3 Figure 3: Summary and HIN schema of the MovieLens 100K (top) and Douban Movie (bottom) datasets. 10

Figure 4 :

 4 Figure 4: Mean individual diversities of different meta-paths Π = R -1 S R X R T for ML100K (a) and DM (b) datasets. S are indicated in rows, T in columns, and X at the bottom for each group of diversities (5 items recommended per user).

Figure 6 :

 6 Figure 6: F1 score for different list sizes of recommended items and different values of α. The meta-paths used are Π(X) and Π(Y ), where X is either Gender or Location (in rows) and Y is either Actors or Type (in columns).

Figure 7 :

 7 Figure 7: Collective and Mean Individual diversities in terms of types of items recommended to users, for different list sizes and recommendation meta-paths modulated by α, for MovieLens 100K dataset (a), and Douban Movie dataset (b).

R 1 Ty- 1 1 Ac

 111 Lo R -1 Lo R likes Location (Lo) R likes R Ty R -Gr R likes Usergroup (Gr) R likes R Ac R -

Figure 8 :

 8 Figure 8: Comparison between recommendations on randomized HINs compared to the original HIN: 0.1-0.9 quantile ranges for F1-score, Mean Individual, and Collective diversities for different list sizes, α values.

  also shows the liking and recommendation relations with dashed lines, R likes and R rec , the latter indicating that a RS may propose a recommendation of an item to a user.

						MovieLens 100K (ML100K)
	Relation	Start Obj. Group	Size	End Obj. Group	Size Links
	R Ty					movie 1664	type	19	2863
	R Ye					movie 1664	release	72	1664
	R rates					user	943	movie 1664 99965
	R Oc					user	943 occupation	21	943
	R Ag					user	943 age group	61	943
	R Ge					user	943	gender	2	943
	R Lo					user	943	location	795	943
	R likes					user	943	movie 1664 82495
			Oc
	Ge							Ty		Ty: Type of film	R Ty : Is of type
	R Ge	R Oc R Lo	U	Rrates R likes Rrec R Ag	I	R Ty R Ye		Ye: Year of release Oc: Occupation Ge: Gender Lo: Location Ag: Age	R Ye : Was released on year R Oc : Has occupation R Ge : Is of gender R Lo : Is in location R Ag : Is of age Rrates: Rates
	Lo							Ye		U: User	R likes : Likes
			Ag					I: Item	Rrec: Is recommended
							Douban Movie (DM)
	Relation		Start Obj. Group	Size	End Obj. Group	Size	Links
	R Ac					movie 6971	actor 3004	15584
	R Di					movie 6971	director	789	3314
	R Ty					movie 6971	type	36	15598
	R Gr					user 3022 usergroup 2269	7054
	R Lo					user 3022	location	244	2491
	R rates					user 3022	movie 6971 195493
	R Fr					user 3022	user 3022	779
	R likes					user 3022	movie 6971 182069
				Lo		Ac
										Ty: Type of film	R Ty : Is of type
		R Lo		Rrates	R Ac		Ac: Actor	R Ac : Stars
	Gr	R Gr		U	R likes Rrec	I	R Di	Di	Di: Director Lo: Location Gr: Group	R Di : Is directed by R Lo : Is in location R Gr : Belongs to R Fr : Is friends with
							R Ty		U: User	Rrates: Rates
		R Fr								I: Item	R likes : Likes
							Ty			Rrec: Is recommended

The codes and data used for these experiments are available at https://github.com/ pedroramaciotti/HINPy

Acknowledgements

We warmly thank Elizabeth Doggett for her proofreading of the manuscript. This work has been funded by the French National Agency of Research (ANR) under grants ANR-15-CE38-0001 (Algodiv), ANR-19-CE38-0006 (GOPI), and ANR LabCom FiT.


Léo Rannou

Clémence Magnien

Matthieu Latapy

Strongly Connected Components in Stream Graphs: Computation and Experimentations

Keywords: Stream Graphs, Link Streams, Temporal Graphs, Temporal Networks, Dynamic Graphs, Connected Components, Algorithms

Stream graphs model highly dynamic networks in which nodes and/or links arrive and/or leave over time. Strongly connected components in stream graphs were defined recently, but no algorithm was provided to compute them. We present here several solutions with polynomial time and space complexities, each with its own strengths and weaknesses. We provide an implementation and experimentally compare the algorithms in a wide variety of practical cases. In addition, we propose an approximation scheme that significantly reduces computation costs, and gives even more insight on the dataset.

Connected components are among the most important concepts of graph theory. They were recently generalized to stream graphs [START_REF] Latapy | Stream graphs and link streams for the modeling of interactions over time[END_REF], a formal object that captures the dynamics of nodes and links over time. Unlike other generalizations available in the literature, these generalized connected components partition the set of temporal nodes. This means that each node at each time instant is in one and only one connected component. This makes these generalized connected components particularly appealing to capture important features of objects modeled by stream graphs. However, computation of connected components in stream graphs has not been explored yet. Therefore, up to this date, they remain a formal object with no practical use. In addition, the algorithmic complexity of the problem is unknown, as well as the insight they may shed on real-world stream graphs of interest.

After introducing key notations and definitions (Section 1), we present two algorithms for strongly connected components, together with their complexity (Section 2). We then apply these algorithms to several large-scale real-world datasets and demonstrate their ability to describe such datasets (Section 3). We also show that their performances may be improved greatly at the cost of reasonable approximations. A stream graph S = (T, V, W, E) is defined [START_REF] Latapy | Stream graphs and link streams for the modeling of interactions over time[END_REF] by a finite set of nodes V , a time interval T ⊆ R, a set of temporal nodes W ⊆ T × V , and a set of links E ⊆ T × V ⊗ V such that (t, uv) ∈ E implies (t, u) ∈ W and (t, v) ∈ W .

The Stream Graph Framework

For any u and v in V , T u = {t, (t, u) ∈ W } denotes the set of time instants at which u is present, and T uv = {t, (t, uv) ∈ E} the set of time instants at which u and v are linked together. We assume that both T u and T uv are unions of a finite number of disjoint closed intervals (possibly singletons) of T . We call node segment a couple ([b, e], u) such that [b, e] is a segment that is not included in any other segment of T u , and we denote by W the set of all node segments in W . We say that b is an arrival of u, and e a departure. We denote by N = |W | the number of node segments in the stream. Likewise, we call link segment a couple ([b, e], uv) such that [b, e] is not included in any other segment of T uv , and by E the set of all link segments in E. We say that b is an arrival of uv, and e a departure. We denote by M = |E| the number of link segments in the stream. We call all time instants that correspond to a node or link arrival or departure an event time. There are at most 2 • N + 2 • M event times. Notice that the intervals considered above may be singletons. Then, b = e and [b, e] = {b} = {e}. See Figure 1 for an illustration.

The induced graph G(S) = (V (S), E(S)) is defined by V (S) = {v, T v = ∅} and E(S) = {uv, ∃t, (t, uv) ∈ E}. We denote by n = |V (S)| and m = |E(S)| its number of nodes and links, respectively. We denote by G t = (V t , E t ) the graph such that V t = {v, (t, v) ∈ W } and E t = {uv, T uv = ∅}. We denote by G - t the graph that corresponds to the nodes and links present between the event time just before t and t: G

- t = (V - t , E - t ) where V - t = {v, ∃t = t, [t , t] ⊆ T v } and E - t = {uv, ∃t = t, [t , t] ⊆ T uv }.
We consider in input a time-ordered sequence of node or link arrivals or departures. We maintain the set of present nodes and links at the current time instant t, i.e. the graph G t , and we store their latest arrival time seen so far.

This has a Θ(N + M ) time and Θ(n + m) space cost for the whole processing of input data. Therefore, these worst-case complexities are lower bounds for our algorithms.

Strongly Connected Components

A strongly connected component of S = (T, V, W, E) is a maximal subset I × X of W such that I is an interval of T and X is a connected component of G t for all t in I. It is denoted by (I, X). The set of all strongly connected components of S is a partition of W [START_REF] Latapy | Stream graphs and link streams for the modeling of interactions over time[END_REF]. See Figure 1 to indicate an interval that can be either open or closed on its extremities. This interval contains ]b, e[ and may or may not contain b and/or e. We will also use mixed notation: b, e] for instance designates an interval that may or may not contain b, but does contain e.

The number of strongly connected components is in Θ(N + M ), because there can be one component per node segment, and each link segment may induce up to four components. Indeed, each beginning of a link segment may correspond to the beginning of two components: one instantaneous at the link segment beginning and one that starts just after; and each link segment ending may correspond to the beginning of two connected components if the corresponding component becomes disconnected. Explicitly writing a component to the output is done in linear time with respect to its number of nodes, in Ω(N + n • M ).

Direct Approach

One may compute strongly connected components directly from their definition, by processing event times in increasing order and by maintaining the set of strongly connected components that begin before or at current event time, and end after it. We represent each such component as a couple ( b, C), meaning that it starts at b (included or not) and involves nodes in C.

More precisely, we start with a set C containing ([α, C) for each connected component C of the graph G α at the first event time α. Then, for each event time t > α in increasing order we consider the connected components of G - t . For each such component C, if there is no component ( b, X) with X = C in C then we add (]t , C) to C , where t is the event time preceding t. For each element ( b, X) of C , if X is not a connected component of G - t , then we remove it from C and we output ( b, t ], X). We then turn to the connected components of G t : for each such component C, if there is no component ( b, X) with X = C in C then we add ([t, C) to C ; and for each element ( b, X) of C , if X is not a connected component of G t , then we remove it from C and we output ( b, t[, X). Finally, when the last event time t = ω is reached, we output ( b, ω], X) for each element ( b, X) of C .

Clearly, this algorithm outputs all strongly connected components of the considered stream graph. Computing the connected components of each graph is in O(n + m) time and space. The considered set families (the graph connected components, as well as the elements of C ) form partitions of V . Therefore, their storage and all set comparisons processed for each event time have a cost in O(n) time and space. There are O(M +N ) event times, therefore, the time complexity of this method is O((N + M ) • (n + m)), and it needs O(n + m) space.

Without changing its time complexity, this algorithm may be improved by ignoring event times t such that all events occurring at t are link arrivals between nodes already in the same connected component. However, one still has to compute graph connected components at each event time with link departures. Therefore, this improvement is mostly appealing if many link departures occur at the same event times.

More generally, the approach above is efficient only if many events (node and/or links arrivals and/or departures) occur at each event time. Then, many connected components may change at each event time, and computing them from scratch makes sense. Instead, if only few events occur at most event times, managing each event itself and updating current connected components accordingly is appealing.

This leads to the following algorithm, which starts with an empty set C , considers each event time t in increasing order, and performs the following operations.

1. For each node segment ([b, e], u) such that b = t (node arrival), add ([b, {u}) to C . 2. For each link segment ([b, e], uv) such that b = t (link arrival), let C u = ( b u , X u ) and C v = ( b v , X v ) be the elements of C such that u ∈ X u and v ∈ X v ; if C u = C v then replace C u and C v by ([t, X u ∪ X v ) in C . Then: if b u = [t then output ( b u , t[, X u ); if b v = [t then output ( b v , t[, X v ). 3. Let G t = G t ; then for each link segment ([b, e], uv) such that e = t (link departure), let C v = C u = ( b u , X u ) be the element of C such that u ∈ X u and v ∈ X u ; remove the link uv from G t ; if there is no path between u and v in G t then replace C u by C u = (]t, X u ) and C v = (]t, X v ) in C where X u and X v are the connected components of u and v in G t , respectively; if b u =]t then output ( b u , t], X u ). 4. For each node segment ([b, e], u) such that e = t (node departure), let C u = ( b u , X u ) be the element of C such that u ∈ X u ; remove C u from C ; if b u =]t then output ( b u , t], {u}).
We call this algorithm SCC Direct. It clearly outputs the strongly connected components of the considered stream, like the previous algorithm. It performs 2(M + N ) of the steps above, corresponding to N node arrivals and departures and M link arrivals and departures. One easily deals with node arrivals and departures in constant time. If a link arrival induces a merge between two components, computing their union is in O(n), as is outputting both components if needed. Thus the complexity for link arrival steps is in O(M • n). Each link departure calls for a computation of the connected components of a graph, and writing a component to the output is in O(n). Thus the complexity for link departure steps is in O(M • (m + n)). We obtain a total time complexity in O(M • (m + n) + N ). The space complexity is still in O(n + m) as above.

Fully Dynamic Approach

The SCC Direct algorithm presented above is strongly related to one of the most classical algorithmic problems in dynamic graph theory, called fully dynamic connectivity [START_REF] Kejlberg-Rasmussen | Faster Worst Case Deterministic Dynamic Connectivity[END_REF][START_REF] Wulff-Nilsen | Faster deterministic fully-dynamic graph connectivity[END_REF][START_REF] Iyer | An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms[END_REF][START_REF] Alberts | An Empirical Study of Dynamic Graph Algorithms[END_REF][START_REF] Huang | Fully dynamic connectivity in O(logn(loglogn) 2 ) amortized expected time[END_REF][START_REF] Kapron | Dynamic Graph Connectivity in Polylogarithmic Worst Case Time[END_REF][START_REF] Henzinger | Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time Per Operation[END_REF], which aims at maintaining the connected components of an evolving graph. Considering a sequence of link additions and removals, dynamic connectivity algorithms maintain a data structure able to tell if two nodes are in the same connected components (query operation) and to merge or split connected components upon link addition or removal (update operation).

This data structure and the corresponding operations can be used in the above algorithm: we can use the data structure to store C , the set of current connected components (we also need to store the beginning time of each component, which has negligible cost). Then, at each link arrival or departure, we can use the query operation to test whether the two nodes are in the same component or not, and the update operation to add or remove the current link to the data structure, while keeping an up-to-date set of connected components. When we observe a node appearance it is necessarily isolated, so we have to add the current time to its component. All the other steps (mainly, writing the output) are unchanged. We call this algorithm SCC FD.

Several methods efficiently solve the dynamic connectivity problem, the key challenge being to know if updates and queries may be performed in O(log(n)) time, where n is the number of nodes in the graph. Current exact solutions per-

form updates in O n•(log log(n)) 2 log(n)
worst time [START_REF] Kejlberg-Rasmussen | Faster Worst Case Deterministic Dynamic Connectivity[END_REF], or in log 2 (n) log log(n) amortized worst time [START_REF] Wulff-Nilsen | Faster deterministic fully-dynamic graph connectivity[END_REF]. Probabilistic (exact or approximate) methods perform even better, but they remain above the O(log(n)) time cost [START_REF] Huang | Fully dynamic connectivity in O(logn(loglogn) 2 ) amortized expected time[END_REF][START_REF] Kapron | Dynamic Graph Connectivity in Polylogarithmic Worst Case Time[END_REF][START_REF] Henzinger | Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time Per Operation[END_REF].

It is well acknowledged that these algorithmic time and space complexities hide big constants, and that the underlying algorithms and data structures are very intricate. As a consequence, implementing these algorithms is an important challenge in itself [START_REF] Alberts | An Empirical Study of Dynamic Graph Algorithms[END_REF][START_REF] Iyer | An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms[END_REF], and the results above should be considered as theoretical bounds. In practice, the implemented algorithms typically have O(log(n) 3 ) amortized time and linear space complexities, still with large constants [START_REF] Alberts | An Empirical Study of Dynamic Graph Algorithms[END_REF][START_REF] Iyer | An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms[END_REF].

In SCC FD, we perform O(M ) updates and queries, which leads to a O(M • polylog(n)) overall time cost for these operations, with any of the polylog dynamic connectivity algorithms cited above. This cost is dominated by the cost of outputting the results, which is in O(M • n). An additional N factor is needed to deal with node arrivals and departures. Hence, we obtain a total time in O(M • n + N ). The space cost of dynamic connectivity methods is in O(m + n • log n), and we do not store significantly more information.

This algorithm is particularly appealing if large connected components are quite stable, i.e. if most largest strongly connected components in the stream have a long duration. Indeed, in this case, fully dynamic update operations are much faster than updates used in SCC Direct, and the output is much smaller than the maximum Ω(N + M • n) bound. The cost of SCC FD is then dominated by fully dynamic operations, and its time complexity is reduced to O(M • polylog(n)).

Experiments and Applications

In this section, we conduct thorough experiments with several real-world datasets and our different algorithms. SCC Direct was significantly faster, and only SCC Direct was able to perform the computation in central memory of large-scale datasets (several dozens of millions of link segments). We publicly provide Python 3 implementations of our algorithms in the Straph library [START_REF] Rannou | Straph -Python Library for the modelisation and analysis of Stream Graphs[END_REF].

Datasets

First notice that most available datasets record instantaneous interactions only, either because of periodic measurements, or because only one timestamp is available. In such situations, one resorts to δ-analysis [START_REF] Latapy | Stream graphs and link streams for the modeling of interactions over time[END_REF]: one considers that each interaction lasts for a given duration δ. This transforms a dataset into a stream graph S = (T, V, W, E) in which all link segments last for at least δ, and all links in D separated by a delay lower than δ lead to a unique link segment. Nodes are considered as present only when they have at least one link.

In order to explore the performances of our algorithms in a wide variety of situations, we considered 14 publicly available datasets that we shortly present below. Their key stream graph properties are given in Table 1, together with the value of δ we used. It either corresponds to a natural value underlying the dataset or is determined by the original timestamp precision. 1: Key features of the real-world stream graphs we consider, ordered with respect to their number M of link segments (K indicates thousands, M millions).

UC Message (UC) [START_REF] Kunegis | Konect: the koblenz network collection[END_REF] is a capture of messages between University of California students in an online community. High School 2012 (HS 2012) [START_REF] Fournet | Contact patterns among high school students[END_REF] is a sensor recording of contacts between students of 5 classes during 7 days in a high school in Marseille, France in 2012. Digg [START_REF] Kunegis | Konect: the koblenz network collection[END_REF] is a set of links representing replies of Digg website users to others. Infectious [START_REF] Isella | What's in a crowd? analysis of face-to-face behavioral networks[END_REF] is a recording of face-to-face contacts between visitors of an exhibition in 2009, Dublin. Twit-ter Higs (Twitter) [START_REF] Domenico | The Anatomy of a Scientific Rumor[END_REF][START_REF] Leskovec | SNAP Datasets: Stanford large network dataset collection[END_REF] is a recording of all kinds of twitter activity for one week around the discovery of the Higgs boson in 2012. Linux Kernel mailing list (Linux) [START_REF] Kunegis | Konect: the koblenz network collection[END_REF] represents the email replies between users on this mailinglist. Facebook wall posts (Facebook) [START_REF] Viswanath | On the evolution of user interaction in facebook[END_REF] represents messages exchanged between Facebook users, through their walls. Epinions [START_REF] Kunegis | Konect: the koblenz network collection[END_REF] is a set of timestamped trust and distrust link creations on Epinions, an online product rating site. Amazon [START_REF] Kunegis | Konect: the koblenz network collection[END_REF] contains product ratings on Amazon. Youtube [START_REF] Mislove | Online Social Networks: Measurement, Analysis, and Applications to Distributed Information Systems[END_REF] is a social network of YouTube users and their friendship connections. Movielens [7] contains movie ratings by users of the Movielens site. Wiki Talk En (Wiki) [START_REF] Kunegis | Konect: the koblenz network collection[END_REF] is a recording of discussions between contributors to the English Wikipedia. Mawilab 2020-03-09 (Mawilab) [START_REF] Fontugne | MAWILab: Combining Diverse Anomaly Detectors for Automated Anomaly Labeling and Performance Benchmarking[END_REF] is a 15 minutes capture of network traffic on a backbone trans-pacific router in Japan on March 3, 2020. Each link represents a packet exchanged between two internet addresses. Stackoverflow [START_REF] Paranjape | Motifs in Temporal Networks[END_REF][START_REF] Leskovec | SNAP Datasets: Stanford large network dataset collection[END_REF] is a recording of interactions on the stack overflow web site. Figure 2 presents the time cost for each dataset, and show a strong relation between the number of link segments, the number of connected components, and computation time. Notice however that Wiki and Mawilab have similar numbers of link and node segments but SCC Direct is several order of magnitude faster on Wiki. This difference comes from their quite different structure regarding connected components: Mawilab has more than 21M SCC involving at least 30K nodes, whereas Wiki has only 2K such SCC. As explained in Section 2, the computational cost of SCC Direct mainly depends on the number of nodes in each SCC, which is observed in this experiment.

Algorithm performances

Connectedness analysis of IP traffic

We take the MawiLab IP traffic capture as a typical instance of large real-world datasets modeled by a stream graph, and we use it to illustrate the relevance of connected component analysis. The stream has 30, 062, 184 such components, with no giant one. Given C = ( b, e , X) we call the number of involved nodes |X| its size, and the length of its time interval e -b its duration.

In Figure 3, we display the strongly connected component size and duration distributions as well as the duration of components as a function of their size. Clearly, component size and duration are not linearly dependant. No component significantly stands out of the crowd: there is no component with both a long duration and a large size. Instead, large strongly connected components have a very short duration, and, conversely, long components have a small size. For instance, all components involving at least 2K nodes have a duration lower than 1e-3 seconds, and all components that last for more than two seconds involve less than ten nodes. The largest component (in terms of number of nodes) involves 49, 791 nodes (only 5.3% of the whole), and lasts for 8.2e-5 seconds (only 9.1e-6% of the whole).

More generally, these plots show that there are many strongly connected components with very short duration: 90% last less than 0.14 seconds. These components are due to the frontier effect, that we define as follows. Consider a set X of nodes, and assume that link segments that start close to a given time b and end close to a given time e connect them. However, they all start at different times and end at different times. This leads to a connected component ([b , e ], X), with b close to b and e close to e, but also to many short strongly connected components that both start and end close to b, or close to e. These components make little sense, if any, but they account for a huge fraction of all strongly connected components, and so they have a crucial impact on computation time as explained in the previous section. We show below how to get rid of them while keeping crucial information.

Approximate Strongly Connected Components

The fact that link segments start and end at slightly different times induces many strongly connected components of very low duration, that have little interest. We, therefore, propose to consider the following approximation of the stream graph S = (T, V, W, E). Given an approximation parameter ∆ < δ and any time t in T , we define t ∆ as ∆ • t ∆ and t ∆ as ∆ • t ∆ . We then define

S ∆ = (T, V, W ∆ , E ∆ ) where W ∆ = ∪ ([b,e],v)∈W [ b ∆ , e ∆ ] × {v} and E ∆ = ∪ ([b,e],uv)∈E [ b ∆ , e ∆ ] × {uv}.
In other words, we replace each node segment ([b, e], v) by a shorter node segment that starts at the first time after b and ends at the last time before e which are multiple of ∆. We proceed similarly with link segments.

First notice that S ∆ is an approximation of S, in the sense that S ∆ may be computed from S, but not the converse. In addition, each node or link segment in S lasts at least δ, and since ∆ is lower than δ, no node or link segment disappears when S is transformed into S ∆ ; only their starting and ending times change. In addition, S ∆ is included in S: W ∆ ⊆ W and E ∆ ⊆ E. This has an important consequence: all paths in S ∆ are also paths in S, and so the approximation does not create any new reachability relation. It, therefore, preserves key information contained in the original stream. Let us first observe the effect of the approximation on strongly connected components in Figure 4. The number of components rapidly drops from its initial value of 30 millions (for ∆ = 0, i.e. no approximation) to less than 6 millions for ∆ = δ/10 3 = 0.002. Its decrease is much slower when ∆ grows further, which indicates that the stream does not anymore contain an important number of irrelevant components due to the frontier effect. As expected, this has a strong impact on computation time, which we also display; it also very rapidly drops, from more than one day to less than one hour, making computations on such large-scale datasets much quicker. Figure 5 presents the effect of ∆ on size, duration and span distributions of strongly connected components. For ∆ = δ/10 4 , we notice that while the number of components has decreased by half only fifty percent of them involve more than 30K nodes. Furthermore, as ∆ increases, the number of components tends to be stable (Figure 4) but the number of components involving more than 30K nodes continues to drop. This explains the differences observed in the execution time of SCC Direct (Figure 4) and confirms that the approximation eliminates most very short connected components, but not all: the ones which are not due to the frontier effect are preserved, another wanted feature. Although the approximation above has a strong impact on the number of strongly connected components, it preserves key information of the stream. We illustrate this by considering one of the most widely studied features of these objects: the latency between nodes [START_REF] Kempe | Connectivity and Inference Problems for Temporal Networks[END_REF][START_REF] Xuan | Computing shortest, fastest, and foremost journeys in dynamic networks[END_REF]. Given two nodes u and v in a stream graph S = (T, V, W, E), the latency from u to v, denoted by (u, v), is the minimal time needed to reach v from u by following links of S in a time-respecting manner, and taking into account node dynamics, see [START_REF] Latapy | Stream graphs and link streams for the modeling of interactions over time[END_REF] for details.

Notice that latencies in S ∆ are necessarily larger than or equal to latencies in S, since paths in S ∆ are also paths in S. Therefore, latencies in S ∆ are upper bounds of latencies in S, and we show below that they are actually quite close.

Figure 6 displays the average difference between latencies in S and S ∆ as a function of ∆ for the Mawi dataset:

u,v∈V,u =v ∆ (u,v)-(u,v) n•(n-1)
. It also displays the average latency stretch u,v∈V,u =v ( ∆ (u,v)+1)/( (u,v)+1)

n•(n-1)
and the latency root mean square error:

LRMSE (S, S ∆ ) = u,v∈V,u =v ( (u,v)-∆ (u,v)) 2 n(n-1)
. The figure also indicates the number of node pairs that were reachable in S but became unreachable in this approximation. It appears that latencies are not significantly impacted by approximation, thus confirming that S ∆ , despite its reduced number of strongly connected components, captures key information available in S. More precisely, only 11 temporal paths disappear for ∆ = δ/10 3 and 115 disap-pear for ∆ = δ/10 2 , among a total number of 2, 888, 917. The over-estimate of latencies is very small, with a LRMSE of 0.51 and 1.61, respectively. This has important consequences. For instance, one may compute latencies in S ∆ from its strongly connected components, which are much easier to compute and store than the ones of S, and obtain this way fast and accurate upper bounds (or approximations) of latencies in S, like we did here for the Mawilab dataset.

Related Work

We focus here on connected components defined in [START_REF] Latapy | Stream graphs and link streams for the modeling of interactions over time[END_REF], but other notions of connected components in dynamic graphs have been proposed. Several rely on the notion of reachability, which, in most cases, induces components that may overlap and are NP-hard to enumerate, see for instance [START_REF] Bhadra | Complexity of Connected Components in Evolving Graphs and the Computation of Multicast Trees in Dynamic Networks[END_REF][START_REF] Gómez-Calzado | A Connectivity Model for Agreement in Dynamic Systems[END_REF][START_REF] Huyghues-Despointes | Forte delta-connexité dans les flots de liens[END_REF][START_REF] Nicosia | Components in time-varying graphs[END_REF]. This makes them quite different from the connected components considered here.

Akradi and Spirakis [START_REF] Akrida | On Verifying and Maintaining Connectivity of Interval Temporal Networks[END_REF] study and propose an algorithm for testing whether a given dynamic graph is connected at all times during a given time interval. If it is not connected, their algorithm looks for large connected components that exist for a long duration. Vernet et al. [START_REF] Vernet | A Study of Connectivity on Dynamic Graphs: Computing Persistent Connected Components[END_REF] propose an algorithm for computing all sets of nodes that remain connected for a given duration, and that are not dominated by other such sets. Unlike our work, these papers do not partition the set of temporal nodes.

Finally, observing the size of largest components is classical, and Nicosia et al. [START_REF] Nicosia | Components in time-varying graphs[END_REF] study them in time-varying graphs, with a connectivity based on reachability through temporal paths. They have a component for each node, which may overlap.

Conclusion

We proposed, implemented, and experimentally assessed a family of polynomial algorithms to compute the connected components of stream graphs. These algorithms handle streams of dozens of millions of events, and output connected components in a streaming fashion. This brings valuable information in practice, as we illustrate on a large-scale real-world dataset. We also propose a dataset approximation scheme making computations much faster while preserving key properties of the original data. Up to our knowledge, it is the first time that a partition of temporal nodes into connected components is computed at such scales.

A promising perspective is to enumerate connected components without listing them: one may for instance output only component size and duration in this way. Fully dynamic algorithms are particularly appealing to this regard, as their complexity is dominated by the explicit component listing.

  Given any two setsA and B, we denote by A ⊗ B the set of pairs ab such that a ∈ A, b ∈ B and a = b. Couples are ordered, while pairs are unordered: (a, b) = (b, a) while ab = ba.

Fig. 1 :

 1 Fig. 1: (Left) An example of stream graph. We display time T = [0, 10] on the horizontal axis and nodes V = {A, B, C, D, E, F } on the vertical one. We represent each node segment by a colored horizontal segment, with one color per node; and each link segment in grey by a vertical line between the two involved nodes at the link segment starting time, and an horizontal line from this time to its ending time. (Right) The 16 strongly connected components of the stream graph.

  for an illustration. Notice that some component time intervals are closed, some are open and some are a combination of the two. For instance, ([0, 1], {C, D}) is a closed component, (]4, 6[, {B}) is an open one, ([6, 7[, {B, C}) is a left-closed and right-open one, and ([4, 4], {A, B, C}) is a closed and instantaneous component. Since the time intervals of components may be open or closed, we introduce the notation b, e

Fig. 2 :

 2 Fig. 2: Time cost of SCC Direct and SCC FD in seconds, along with the number M of link segments and the number of strongly connected components, for each considered stream (horizontal axis, ordered with respect to M ).

Fig. 3 :

 3 Fig. 3: Distribution of the size (left) and duration (middle) of SCC in Mawilab dataset. Duration of each SCC as a function of its size, in log-log scales (right).

Fig. 4 :

 4 Fig. 4: Running time of SCC Direct, number of SCC and number of event times in MawiLab, as a function of ∆ (here, δ = 2s).

Fig. 5 :

 5 Fig. 5: Box plots representing the distribution of the size (left), duration (middle) and span (right) of strongly connected components in Mawilab, for various values of ∆ (here, δ = 2s). We indicate the mean, minimal, and maximal values with dots connected by horizontal lines, as well as the median and percentiles with vertical boxes.

Fig. 6 :

 6 Fig.6: Evolution of the LRMSE, the average difference between latencies and the average latency stretch with respect to ∆ in Mawilab. We indicate the number of missing paths and represent it as a disk of area proportional to this number.

Table

		δ	n	m	|T | N	M
	UC	1h 2K	14K 189d 43K 34K
	HS 2012	60s 327 6K	4d	48K 46K
	Digg	1h 30K 85K 14.5d 110K 86K
	Infectious	60s 11K 45K 80d 85K 133K
	Twitter	600s 304K 452K 7d	543K 488K
	Linux	10h 27K 160K 8y	450K 544K
	Facebook	10h 46K 183K 4.3y 957K 588K
	Epinions	10h 132K 711K 2.6y 404K 743 K
	Amazon	1h 2.1M 5.7M 9.5y 9.9M 5.8M
	Youtube	24h 3.2 M 9.4M 226d 6.7M 9.4M
	Movielens	1h 70K 10M 14y 8.5M 10M
	Wiki	1h 2.9M 8.1M 14.3y 18.3M 14.5M
	Mawilab	2s 940K 9.1M 902s 17M 18.8M
	Stackoverflow 10h 2.6M 28.2M 7.6y 30M 33.5 M