INTEGRATIVE METHODS FOR ROBUST NETWORK ANALYSIS

Abstract

Networks (or graphs) are natural representations for big linked data, which are ubiquitous in the increasingly interconnected world. Because of their prevalence and importance, techniques for network analysis such as node ranking, clustering, embedding and anomaly detection, have gained substantial research interests recently. Despite the encouraging achievements in the development of these algorithms, most of the current research efforts have been devoted to single network analysis. A major drawback of individually analyzing a network is that the results are largely subject to the noises and incompleteness of a single network.

As the rapid growing data from multiple information sources, domains and conditions are getting more and more interdependent, nowadays it is less reasonable than before to simply consider networks as being existing in isolation. Instead, multiple interrelated networks appear to be a common phenomenon in a variety of fields ranging from manufacturing, business to biology and medicine. The wide emergence of multi-network data, together with their inter-dependencies, necessitates integrative analysis. By integrating multiple networks, compatible and complementary information can be exploited to refine the pattern mining process, which is promising to overcome the limitation of single network analysis and can help obtain a more accurate and robust performance in a mining task.

In this dissertation, I investigate the principles and methodologies of integrative analysis on multi-network data. Basically, the various multi-network data are summarized by three major categories – multi-view network, multi-domain network and temporally ordered networks. For each of them, this dissertation identifies the unique challenges, discusses current progresses, and proposes effective solutions. The goal of this dissertation is to shed some light on effectively managing, analyzing and utilizing multi-network data in real-world applications.

dedicated to my family.

 

Chapter 1 |

Introduction

Nowadays, data entities in our world are increasingly interacting with or impacting on each other, making networked data ubiquitous in our daily life. Examples include social networks [1] , the World Wide Web, transportation networks [2] , infrastructure networks [3] , biological networks [4] , medical networks [5] , and so on. Because of their prevalence, tremendous research attentions have been drawn to network analysis, which has become a central topic in modern data science [6,7] . Fruitful discoveries from networked data have been found useful in wide fields from manufacturing, business to biology and medicine [7] . Clearly, the study of networked data is of significant importance in a variety of real-world applications.

In most of the current researches on network data analysis, networks are often studied individually. In other words, each time, one network is fed to a mining algorithm to discover useful patterns or properties. This intuitive manner, however, inevitably ignores the potential relationships between different networks, and is subject to significant information loss. In fact, as the rapid growing data from multiple sources, domains and conditions are getting more and more interdependent, nowadays it is no longer reasonable to simply consider networks as being existing in isolation. Instead, multiple networks, which are interrelated in various forms, appear to be a common phenomenon in wide domains [8] .

For example, nowadays online users are often involved in more than one social network. As a result, multiple social networks from Facebook, LinkedIn, Youtube, etc. are related one another by those common users. Fig. 1.1(a) illustrates this example, where the three social networks are collected from different social medias. Some users in them are common (e.g., U₁, U₂, U₃) while others are unique (e.g.,

U₈, U₉, U₁₀). In this scenario, there is a one-to-one correspondence between users

Social Network 1                       Social Network 2                       Social Network 3

Figure 1.1. Examples of multi-network. In (b), the dotted lines represent cross-network relationships. The value on each dotted line indicates the weight of the relationship. In (c), red edges represent vanishing edges, green edges represent new edges.

from different networks, which represents the identity of users across different social networks, e.g., U₁ represents the same user who appears in all networks.

In some other applications, nodes in different networks may represent different entities. Fig. 1.1(b) shows a different type of multi-network. In this case, multiple networks may contain nodes of different domains, such as text documents, online users and color images. Here, text-text links are formed by the hyper-links between different Web documents. Users are involved in a social network. Images cooccurring within the same Web page provide explicit linkages between them. Moreover, users may interact with texts and images by responding to them or clicking on them, which forms the cross-network relationships that interconnect multiple networks, as represented by the dotted lines in Fig. 1.1(b). In this scenario, the mappings between nodes in different networks may form a many-

to-many correspondence, instead of one-to-one, e.g., one user may interact with multiple Web documents, and vice versa.

Moreover, the structure of a network may change over time, resulting in multiple networks in a sequential order, where each network represents a snapshot at a particular time point [9] . Fig. 1.1(c) illustrates a sequence of time-varying social networks. At each time point, existing users may vanish (e.g.,U₁ from Time 1 to

Time 2, U₂ from Time 2 to Time 3) and new users may join in (e.g., U₃ at Time 2, U₄ at Time 3). Similarly, existing edges may break at a time point (e.g., red edges) and new edges may establish (e.g., green edges). In this scenario, multiple networks are ordered temporally, and there is a one-to-one and directional correspondence pointing from the users in one network to the users in its subsequent network, which represents the identities of users over time.

Basically, the various multi-network data are covered by three major categories – multi-view network [10–14] ,multi-domain network [5,15,16] andtemporally ordered networks [9,17] , which will be thoroughly discussed throughout this dissertation. Next, we briefly introduce different types of multi-network data.

1.1 Categories of Multi-Network

Studies of multi-network are increasingly essential in wide disciplines. As a result, various terminologies describing different types of multi-network data have appeared in literature. This dissertation focuses on three major categories of multi-network as following, which cover most cases in real applications. A comprehensive review summarizing different terminologies of multi-network and their relationships can be found in [8] .

Multi-View Network. In Fig. 1.1(a), we have seen a concrete example of multi-view network, in which multiple social networks are interrelated by common users. Here, different networks encode different aspects of the social relationships between users {U₁,…,U₁₀}, such as the friendships on Facebook, the co-working relationships on LinkedIn and the video-sharing relationships on Youtube. Therefore, each network can be regarded as a particular “view” about the relationships between users. Different views share some consistent information, meanwhile provide complementary information. Hence, integrating them is crucial to obtain a complete and accurate analysis about the heterogeneous social relationships.

Multi-view networks are prevalent in our life. As another example, the public transportation network of a particular region (e.g., a country) has multiple views, including the airline network, the rail network, the subway network, the coach network, and so on [2] . In each network, a node represents a location (e.g., stops, stations, airports), and an edge indicates a traffic line. Here, different views are related by common locations. Only by integrating multiple views together, can we have a full understanding about the traffic status in the region of interest.

Figure 1.2. A general representation of multi-view network.

Fig. 1.2 illustrates a general representation of multi-view network. From Fig.

1.2, we summarize several characteristics of multi-view network as following.

• Different networks are about the same set of nodes (e.g., users).
• There is a one-to-one mapping between nodes in different networks.
• Different networks may have different sizes (i.e., number of nodes).
• Different networks may have different topological structures.

Multi-Domain Network. Fig. 1.1(b) is a concrete example of multi-domain network. Here, multiple networks from heterogeneous domains (e.g., text, user and image) are interconnected by cross-network relationships. Different networks contain different sets of nodes, and consequently, have different structures. The cross-network relationships form a many-to-many mapping because a node in one domain may interact with multiple nodes in another.

Similar examples can also be found in the information networks of many other applications. In bioinformatics, one important problem is to classify genetic diseases in a disease similarity network [18] . In this network, each node is a disease, and each edge depicts the phenotype similarity between two diseases [19] . To reflect the molecular foundation, we may explore the disease similarity network together with its underlying protein-protein interaction (PPI) network, where disease nodes and protein nodes are related one another via the known disease-protein associations [4] . The disease-protein associations form a many-to-many mapping. This is because multiple proteins can function synergistically to cause a single disease and a single protein can participate in the formation of multiple diseases.

Figure 1.3. A general representation of multi-domain network.

Fig. 1.3 illustrates a general representation of multi-domain network. From Fig. 1.3, we summarize several characteristics of multi-domain network as following.

• Different networks may have different sets of nodes thus have different sizes.
• The cross-network relationships may form a many-to-many mapping between nodes in different networks.
• Each cross-network relationship may be associated with an edge weight.
• Some nodes in one network may not have corresponding node in another, making the cross-network relationship an incomplete, partial

In the previous social and biological applications, all these characteristics can be observed. For instance, in Fig. 1.1(b), a user-image relationship may be weighted by the frequency of the interaction. In the biological example, domain experts may specify weights on the disease-protein relationships using their prior knowledge, so as to mark the correlation levels of some disease-protein pairs.

Temporally Ordered Networks. Temporally ordered networks are different from the above two kinds of multi-network data, mainly because of the time dependency between consecutive networks and the latent evolving patterns underlying the networks. In addition to the social networks as shown in Fig 1.1(c), we can find other examples in a variety of fields. For instance, in manufacturing, a cyberphysical system (CPS) can be modeled by a network with each node representing a system component and each edge depicting the dependency relationship between two connected components [9] . Because the running system is monitored over time, the monitoring log data can generate a sequence of networks [17] . These networks record the dynamic status of the relationships between different system components. As another example, in neurology, researchers often construct a brain network to analyze the functional architecture of an individual’s brain. In this network, each node represents a region of the brain (e.g., a voxel of fMRI scans [20] ), and an edge indicates the correlation between two linked nodes. A sequence of brain networks can be generated at different time so as to understand the dynamic activities of human brains [20,21] .

Similar to multi-view network, temporally ordered networks (1) are about the same set of nodes (e.g., users), (2) may have different sizes, and (3) may have different topological structures. However, temporally ordered networks are characterized by the consecutive order, and the evolving patterns underlying the structural changes of these networks.

Remark. Note these three categories of multi-network are not orthogonal to each other. In complicated applications, it is possible to see a combination of them. For example, we can incorporate multiple views of the social networks of Fig. 1.1(a) into the multi-domain network of Fig. 1.1(b) [16] . We can also track the changes of multi-view network in Fig. 1.1(a) over time to obtain temporally ordered multi-view networks. Despite the complexity, these three basic categories can provide us a very fundamental understanding about the multi-network data in real practice.

1.2 Tasks of Network Analysis

Network analysis has been shown to be very beneficial in various areas such as data mining [22] , machine learning [23] , bioinformatics [18] , medicine [7] , and so on. Given a network, the very first question is what can we learn from it. In the following, we summarize several fundamental mining tasks that have been found extremely useful in real-world applications.

Ranking. The task of ranking aims to evaluate the nodes in networks based on some ranking function that mathematically demonstrates characteristics of nodes. With such functions, two nodes can be compared, either qualitatively or quantitatively, in certain order. Ranking techniques have been extensively used in different scenarios, including similarity search [24] , link prediction [22] , recommendation [25] , disease gene prioritization [26] , drug repositioning [27] , etc. In the past decade, a number of algorithms have been proposed to rank nodes in a single network, such as PageRank [28] , HITS [29] , SimRank [30] , etc. A comprehensive survey that compares different ranking algorithms can be found in [22] . In contrast, ranking algorithms on multi-network data are far from welldeveloped, which remains a challenging task in modern network science. We will discuss this topic in Chapter 2 of this dissertation.

Clustering. The goal of network clustering is to decompose a network into multiple sub-components, such that there are many edges within each component but few edges between them. In other words, it aims to identify dense regions in a network. In literature, network clustering is also referred to as community detection [6] . Identifying clusters in a network is a very popular topic in network analysis. By clustering a network, a compact structure can be created for quickly understanding the network, and for efficient storage, query and search of the network data. Clustering techniques have been shown to be useful in numerous applications including social analysis [31] , system debugging [9] , gene pathway analysis [32] , etc. The survey in [6] provides a thorough discussion on this topic. Compared to single network clustering, multi-network clustering is a younger area, which is a topic to be discussed in Chapter 3 of this dissertation.

Embedding. Network data are characterized by the complex relationships between nodes. To analyze network data, one fundamental problem is to resolve the dependencies between nodes and learn compact vector representation for each node, such that the network structure is preserved in the learned vector space [23] . By doing so, network analysis such as node classification [33] , node clustering [34] and link prediction [35] can then be readily performed in vector space by using the vast off-the-shelf machine learning algorithms. Usually, learning network representation is also known as network embedding [23] . The low-dimensional vectors to be learned are called node embeddings. Network embedding finds its importance recently, partially because of the general research trends on representation learning [36,37] . The review in [38] provides a summary about recent embedding algorithms. Although extensive studies have been performed on embedding a single network, how to learn useful embeddings from multi-network remains an open question, which will be discussed in Chapter 4 of this dissertation.

Anomaly Detection. The branch of data mining concerned with discovering rare occurrences in datasets is called anomaly detection. This is a vital task, with numerous high-impact applications in areas such as security, finance, health care and system management [39] . Network-based anomaly detection has drawn a lot of interests, either in static network or dynamic networks. In a static network, the main task is to spot anomalous network entities, including nodes, edges, and subgraphs. For example, OddBall [40] is a technique designed to detect anomalous nodes in a weighted network. In dynamic networks, a number of methods have been proposed to detect abnormal events, and the time stamps when those events take place [41] . A thorough survey about network-based anomaly detection can be found in [39] . Because of the complexity of network evolutions, many challenges on detecting anomalies in dynamic networks are remained to explore. In Chapter 5, we will discuss more about this topic.

1.3 Motivation of Integrative Analysis

Because of the importance of multi-network data in real-world applications, in this dissertation, I investigate the principles and methodologies for mining multiple networks in an integrative manner. Basically, the advantages of integrative analysis are threefold, which are summarized as following.

Complementary Information. Usually, one network only provides us a partial understanding about the knowledge to be mined, while multiple related networks carry complementary information that is closer to the truth. Therefore, integrating them is promising to improve the accuracy of a mining algorithm.

Robustness. In real practice, because of measurement errors and data access limitations, a single network may contain dummy nodes and false links (i.e., noises), and missing nodes and missing links (i.e., incompleteness). Such defects can largely reduce the quality of the mined patterns. Whereas, the false or missing information in one network may be corrected in other related networks. Therefore, integrating them as a whole allows a more robust analysis than treating them in pieces.

Novel Patterns. By leveraging networks from multiple sources or conditions, we can extract novel patterns that cannot be discovered by analyzing each network separately. For example, from multiple social networks, we can identify which communities consistently occur among them, which may represent interesting groups of users that are most active across different social platforms. This pattern, however, cannot be detected from an individual social network.

1.4 Research Challenges

Integrative multi-network analysis is promising. Meanwhile, it is challenging. For the three categories of multi-network as introduced in Sec. 1.1, the challenges are primarily variety, heterogeneity, and dynamics, respectively.

Variety. Obtained from diverse sources, while multi-view networks bear complementary information, they display variety and discrepancy in structures. Taking the clustering structure for example. In a gene co-expression network, a set of nodes (i.e., genes) may form a cluster (e.g., a gene pathway) if they synergistically perform a certain function (e.g., transcribe a protein) [11] . When multiple such networks are collected from different human tissues, several genes may form the same cluster in some correlated tissues, but can belong to different clusters in other tissues. In this case, multiple networks may show a remarkable discrepancy in their clustering structures. This phenomenon often happens in emerging applications [11,12,14] . Hence, it is important to design flexible methods that can handle such variety.

Heterogeneity. To analyze multi-domain network, one key issue is to deal with data collected from heterogeneous information sources that may involve many different types of nodes and edges interrelated in a complex way. As a result of the heterogeneity, the cross-network relationships may form a many-to-many mapping between nodes in different networks, which may be weighted, incomplete and noisy in the mean time, as illustrated in Fig. 1.3. To effectively integrate such networks, one primary challenge thus is how to leverage these complex cross-network relationships to refine a mining procedure.

Dynamics. When considering the temporally ordered networks, one need to model the dynamics of a network. In other words, a mining algorithm should be able to capture the evolutionary patterns, such as the propagation of information [9,17] , in continuous networks. The challenges of modeling the dynamics are three-fold. First, how to identify evolutionary patterns and differentiate them from static patterns and environmental noises. Second, how to model the evolutionary patterns over time. Third, how to detect the sources (or reasons) of the structural changes in evolving networks. The answers to these questions are important toward understanding temporally ordered networks.

1.5 Organization

The first chapter presents an overview of the integrative analysis on multi-network data. The rest of the dissertation is composed of four parts, each of them targets to the methods to a particular mining task, as introduced in Sec. 1.2, in a certain scenario of multi-network. When handling multi-network data, the fundamental mining tasks may present novel and unique challenges. In each part of the dissertation, we will identify these challenges and propose our solutions.

From the perspective of the categories of multi-network data as introduced in Sec. 1.1, the first two parts of the dissertation study a generalization of multi-view network, the third part discusses multi-domain network, and the last part discusses temporally ordered networks. Specifically, the rest of this dissertation is organized as following.

Chapter 2. In this chapter, we first introduce a novel generalization of multi-view network, which is called Network of Networks (NoN), by introducing the similarity information between different networks. Then we discuss a new ranking task and a new similarity search task on an NoN. To address them, we propose an effective ranking algorithm and an efficient similarity search algorithm, and evaluate their performance on various datasets.

Chapter 3. In this chapter, we study a new multi-network clustering problem that has a unique challenge because of the variety of network structures. To handle it, we introduce a new concept, network grouping, into multi-network clustering, based on modeling the data as a network of networks. Then we propose a flexible and robust algorithm that can effectively incorporate network grouping information to refine multi-network clustering, hence address this task.

Chapters 4. In this chapter, we turn our attention to multi-domain networks and introduce a new multi-network embedding problem. In particular, we discuss on how to model the complex relationships in multi-domain network, and propose a general algorithm to learn deep embeddings of nodes to resolve the complex relationships within each network and across different networks.

Chapters 5. This chapter focuses on modeling the evolutionary patterns in temporally ordered networks. In particular, we discuss on how to model the evolutionary patterns of information propagation in the networks. A new technique that considers the local propagations of information will be introduced, together with an important application of causal anomaly detection for complex system diagnosis and management.

Finally, in Chapter 6, we conclude the dissertation and highlight some future research directions.

INTEGRATIVE METHODS FOR ROBUST NETWORK ANALYSIS

Sharing is caring!