Search

Role/block discovery is an essential task in network analytics so it has attracted significant attention recently. Previous studies on role discovery either relied on first or second-order structural information to group nodes but neglected the higher-order information or required the number of roles/blocks as the input which may be unknown in practice. To overcome these limitations, in this paper we propose a novel generative model, infinite motif stochastic blockmodel (IMM), for role discovery in networks. IMM takes advantage of high-order motifs in the generative process and it is a nonparametric Bayesian model which can automatically infer the number of roles. To validate the effectiveness of IMM, we conduct experiments on synthetic and real-world networks. The obtained results demonstrate IMM outperforms other blockmodels in role discovery task.

Role discovery and community detection in networks are two essential tasks in network analytics where the role denotes the global structural patterns of nodes in networks and the community represents the local connections of nodes in networks. Previous studies viewed these two tasks orthogonally and solved them independently while the relation between them has been totally neglected. However, it is intuitive that roles and communities in a network are correlated and complementary to each other. In this paper, we propose a novel model for simultaneous roles and communities detection (REACT) in networks. REACT uses non-negative matrix tri-factorization (NMTF) to detect roles and communities and utilizes L2,1 norm as the regularization to capture the diversity relation between roles and communities. The proposed model has several advantages comparing with other existing methods: (1) it incorporates the diversity relation between roles and communities to detect them simultaneously using a unified model, and (2) it provides extra information about the interaction patterns between roles and between communities using NMTF. To analyze the performance of REACT, we conduct experiments on several real-world SNs from different domains. By comparing with state-of-the-art community detection and role discovery methods, the obtained results demonstrate REACT performs best for both role and community detection tasks. Moreover, our model provides a better interpretation for the interaction patterns between communities and between roles.

Graphs are a fundamental data structure to represent objects and their relations in various domains, e.g., social science, citation analysis, web link analysis, and navigation systems. Reachability and shortest path queries are two types of primitive and well-studied graph queries. In this thesis, we investigate on how to build efficient index structures to answer the reachability queries and two variants of the shortest path queries. The first variant of the shortest path query considers the shortest path in timetable graphs, where it requires the consideration of spatiotemporal constraints between different edges. The second variant aims to provide the shortest path under an additional cost constraint. These problems find many real world applications, and are challenging to achieve high efficiency on sizable graphs. First, we study the reachability queries on directed graphs. Given a directed graph $G$, a source $s$, and a target $t$, a reachability query asks whether there exists a path from $s$ to $t$ in $G$. The state-of-the-art solutions for answering reachability queries are a class of labelling schemes referred to as {\em Hierarchical Hub Labelings (HHL)}. One distinct characteristic of {\em HHL} is that any {\em HHL} index implicitly or explicitly defines a total order of vertices in the graph, and the performance of the index is solely decided by the ordering. Several heuristic approaches have been proposed for vertex ordering in {\em HHL}, but none of them provides any worst-case guarantee. We present a novel study on the vertex ordering in {\em HHL}, and devise a polynomial-time algorithm for vertex ordering that yields an {\em HHL} index whose size is at most $O(\sqrt{n})$ times the optimal one. Motivated by our theoretical study, we design a new heuristic for vertex ordering, and show that it leads to an {\em HHL} index with superior practical performance for reachability queries. Besides, identifying fast routes in public transportation networks is an important problem with applications in map services and navigation systems. In public transportation networks, any traversal between different network locations relies on transportation services (e.g., buses, subways, and ferries.) that run on fixed routes with pre-defined schedules. A public transportation network can often be modeled as a timetable graph where (i) each node represents a station; and (ii) each directed edge $\langle u, v\rangle $ is associated with a timetable that records the departure (resp. arrival) time of each vehicle at station $u$ (resp. $v$). There are several types of shortest path queries on timetable graphs. We study three types of shortest path queries for route planning that have been extensively studied on timetable graphs: {\em earliest arrival path (EAP)}, {\em latest departure path (LDP)}, and {\em shortest duration path (SDP)} queries. These three types of queries aim to find a path that arrives at a place as early as possible, departs as late as possible but arrives on time, and has the shortest travel time, respectively. We present {\em Timetable Labelling (TTL)}, an efficient indexing technique for shortest path queries on timetable graphs. The basic idea of {\em TTL} is to associate each node $u$ with a set of labels, each of which records the shortest travel time from $u$ to some other node $v$ given a certain departure time from $u$; such labels would then be used during query processing to improve efficiency. In addition, we propose query algorithms that enable {\em TTL} to support EAP, LDP, and SDP queries, and investigate how we reduce the space consumption of {\em TTL} with advanced preprocessing and label compression methods. By conducting an extensive set of experiments on real world datasets, we demonstrate that {\em TTL} significantly outperforms the states of the art in terms of query efficiency, while incurring moderate preprocessing and space overheads. Finally, {\em constrained shortest path (CSP)} is a variant of the shortest path problem with an additional total cost constraint. Specifically, in a CSP query, each edge in the road network is associated with both a length and a cost, e.g., travel distance and time. Given an origin $s$, a destination $t$, and a cost constraint $\theta$, the goal is to find the path from $s$ to $t$ that minimizes its total length, while satisfying that its total cost does not exceed $\theta$. Deriving the exact answer for a CSP query has been proven to be NP-hard, and the majority of previous work focuses on approximate solutions. We propose {\em COLA}, the first practical solution for approximate CSP processing on large road networks. {\em COLA} exploits the facts that a road network can be effectively partitioned, and that there exists a relatively small set of landmark vertices that commonly appear in CSP results. Meanwhile, {\em COLA} includes both an effective indexing scheme for partition boundary vertices, and an efficient on-the-fly algorithm called $\alpha$-Dijk for path computation within a partition. Extensive experiments demonstrate that on continent-sized networks with tens of millions of vertices, {\em COLA} answers an approximate CSP query in sub-second time, whereas existing methods take hours. Interestingly, even without an index, the $\alpha$-Dijk algorithm in {\em COLA} still outperforms previous solutions by more than an order of magnitude. DOCTOR OF PHILOSOPHY (SCE)

Graphs provide a natural way to represent real-world objects and their relationships, and hence they are utilized to model concepts and data in various domains, such as social networks, the Web, biological informatics and spatial databases. In the big data era, most graphs are extremely large and growing rapidly in size, which brings challenges to processing graph queries e ciently. In this thesis, we investigate three important problems in graph query processing, namely, the point-to-point shortest path and distance queries on road networks, the single source shortest path and distance queries on diskresident graphs, and the point-to-point reachability queries on dynamic graphs. These problems are not only interesting in themselves when the graph size becomes large, but also fundamental building blocks of numerous real-world applications. In particular, given two locations s and t in a road network, a point-to-point distance query returns the minimum network distance from s to t, while a point-to-point shortest path query computes the actual route that achieves the minimum distance. To solve this problem, we propose Arterial Hierarchy (AH), an index structure that narrows the gap between theory and practice. On the theoretical side, we show that, based on a realistic characteristic of real-world road networks, AH answers any distance query in constant time. In addition, any shortest path query can be answered with k more steps, where k is the number of vertices on the shortest path. On the practical side, AH outperforms the state-of-the-art methods in terms of query time and its space and pre-computation overheads are moderate. Then, given a vertex s in a graph G, a single source shortest distance query from s asks for the distance from s to every other vertex in G, while a single source shortest path query retrieves the shortest path from s to any other vertex. To handle these two types of queries on disk-resident graphs, we propose Highways-on-disk (HoD), a disk-based index that supports both shortest path and distance queries on directed and weighted graphs. Di erent from existing methods, HoD does not assume the graph ts into memory, does not limit the graph type as undirected graph, and does not restrict that the edges have unit weights or even integer weights. Although being more general and exible, HoD is still able to outperform the state-of-the-art methods in terms of query processing time by up to two orders of magnitude. In addition, HoD has a smaller space consumption and pre-computation time in most cases. Finally, given two vertices s and t in G, a reachability query from s to t asks whether there exists a path from s to t in G. To solve the problem on dynamic graphs, we rsti propose the Total Order Labeling (TOL) framework, which summarizes three most advanced methods [22,51,94] for reachability queries on static graphs. Then we investigate novel algorithms to handle updates of TOL, regarding both insertions and deletions on dynamic graphs. To our best knowledge, this is the rst practically e cient and scalable approach that handles the point-to-point reachability queries on dynamic graphs. Finally we propose a new reachability index Butter y, which o ers reduced preprocessing, space, and query costs than any existing indices under TOL [22,51,94]. We experimentally evaluate TOL using a large variety of benchmark datasets with up to twenty million vertices, and we demonstrate the superiority of TOL against alternative solutions for static and dynamic graphs. DOCTOR OF PHILOSOPHY (SCE)

Evaluating a community detection method involvesmeasuring the extent to which the resulted solution, i.e clustering,is similar to an optimal solution, a ground truth. Differentnormalized similarity indices have been proposed in the literatureto quantify the extent to which two clusterings are similar where1 refers to a perfect agreement between them (i.e the two clusterings are identical) and 0 refers to a perfect disagreement. Whileinterpreting the similarity score 1 seems to be intuitive, it does notseem to be so when the similarity score is otherwise suggestinga level of disagreement between the compared clusterings. Thatis because there is no universal definition of dissimilarity whenit comes to comparing two clusterings. In this paper, we addressthis issue by first providing a taxonomy of similarity indicescommonly used for evaluating community detection solutions.We then elaborate on the meaning of clusterings dissimilarityand the types of possible dissimilarities that can exist among twoclusterings in the context of community detection. We perform anextensive evaluation to study the behaviour of different similarityindices as a function of the dissimilarity type with both disjointand non-disjoint clusterings. We finally provide practitioners withsome insights on which similarity indices to use for the task athand and how to interpret their values

Modern graph embedding procedures can efficiently process graphs with millions of nodes. In this paper, we propose GEMSEC – a graph embedding algorithm which learns a clustering of the nodes simultaneously with computing their embedding. GEMSEC is a general extension of earlier work in the domain of sequence-based graph embedding. GEMSEC places nodes in an abstract feature space where the vertex features minimize the negative log-likelihood of preserving sampled vertex neighborhoods, and it incorporates known social network properties through a machine learning regularization. We present two new social network datasets and show that by simultaneously considering the embedding and clustering problems with respect to social properties, GEMSEC extracts high-quality clusters competitive with or superior to other community detection algorithms. In experiments, the method is found to be computationally efficient and robust to the choice of hyperparameters.

Graph data has been so prevalent that efficiently obtaining useful information from them is highly demanded. Given massive amounts of graph data, people are often interested in a small portion, namely their subgraphs, by the processes of mining and querying. Due to the enormous number of subgraphs in the massive graph data, these processes are highly costly. In this thesis, we study three important problems on subgraph mining and query processing, i.e., frequent subgraph mining, network motif discovery, and generalized subgraph query processing. These problems find numerous applications in real world, whereas they are extremely challenging.% since subgraph isomorphism testing is NP-hard. First, mining frequent subgraphs from a large collection of graph objects is an important problem in several application domains such as bio-informatics, social networks, computer vision, etc. The main challenge in subgraph mining is efficiency, as (i) testing for graph isomorphisms is computationally intensive, and (ii) the cardinality of the graph collection to be mined may be very large. We propose a two-step {\em filter-and-refinement} approach that is suitable to massive parallelization within the scalable MapReduce computing model. We partition the collection of graphs among worker nodes, and each worker applies the filter step to determine a set of candidate subgraphs that are {\em locally frequent} in its partition. The union of all such graphs is the input to the refinement step, where each candidate is checked against all partitions and only the {\em globally frequent} graphs are retained. We devise a statistical threshold mechanism that allows us to predict which subgraphs have a high chance to become globally frequent, and thus reduce the computational overhead in the refinement step. We also propose effective strategies to avoid redundant computation in each round when searching for candidate graphs, as well as a lightweight graph compression mechanism to reduce the communication cost between machines. Extensive experimental evaluation results on several real-world large graph datasets show that the proposed approach clearly outperforms the existing state-of-the-art and provides a practical solution to the problem of frequent subgraph mining for massive collections of graphs. Second, the identification of network motifs has essential applications in numerous domains, such as pattern detection in biological networks and graph analysis in digital circuits. However, mining network motifs is computationally challenging, as it requires to enumerate subgraphs from a real-life graph, and compute the frequency of each subgraph in a large number of random graphs. In particular, existing solutions often require days to derive network motifs from biological networks with only a few thousand vertices. To address this problem, this thesis presents a novel study on network motif discovery using Graphical Processing Units (GPUs). The basic idea is to employ GPUs to parallelize a large number of subgraph matching tasks in computing subgraph frequencies from random graphs, so as to reduce the overall computation time of network motif discovery. We explore the design space of GPU-based subgraph matching algorithms, with careful analysis of several crucial factors that affect the performance of GPU programs. Based on our analysis, we develop a GPU-based solution that (i) drastically differs from existing CPU-based methods, and (ii) exploits the strengths of GPUs in terms of parallelism while mitigating their limitations in terms of the computation power per GPU core. With extensive experiments on a variety of biological networks, we show that our solution is up to two orders of magnitude faster than the best CPU-based approach, and is around $20$ times more cost-effective than the latter, when taking into account the monetary costs of the CPU and GPUs used. Finally, we study a new type of graph queries, which injectively maps its edges to paths of the graphs in a given database, where the length of each path is constrained by a given threshold specified by the weight of the corresponding matching edge. We give important applications of the new graph query and identify new challenges of processing such a query. In particular, the new type of graph queries further explodes the already exponential search space compared with conventional graph queries. Besides, existing pruning techniques cannot be directly applied or they are simply not adequate, since our new type of query graphs is different from their indexed features. To address these issues, we devise the cost model of the branch-and-bound algorithm framework for processing the graph query, and propose an efficient algorithm to minimize the cost overhead. We also develop three indexing techniques to efficiently answer the queries online, each of which can be applied into different scenarios. Finally, we verify the efficiency of our proposed indexes with extensive experiments on large real and synthetic datasets. DOCTOR OF PHILOSOPHY (SCE)

Deep Learning and Learning to Hash are two important research areas in machine learning, which have rapid improvements in recent years. What I mainly researched on is an inter-discipline field: deep learning for cross view hashing. Multiple layers of representation in deep learning has the property of abstracting representation from input data, while, in the cross view similarity search, the biggest difficulty is to represent items from one domain to another. Here, I want to take advantage of the latest deep learning technology to solve the cross view similarity search problem. Hashing is used to accelerate this process. This thesis mainly contains three parts. Chapter 2 is a literature survey. It contains a deep learning survey and a learning to hash survey. The deep learning survey briefly introduces fundamental technology of deep learning and its recent development including the latest technology. The Learning to Hash survey brief introduces some widely used learning to hash algorithms. Chapter 3 is an experiment about comparison of some state of the arts learning to hash algorithms. Chapter 4 is cross view hashing based on deep learning. I present a cross view feature hashing technique using deep learning and show some results. These three chapters are main chapters. Chapter 1 and Chapter 5 are introduction and conclusion. MASTER OF ENGINEERING (SCE)