Network embedding (NE) aims to learn low dimensional node representations, wherein both neural-based (NNE) and factorization-based (FNE) methods commonly employ negative sampling (NS) as an essential component. However, the role of NS differs markedly between these two paradigms: in NNE, negative samples are randomly chosen to facilitate efficient training, while in FNE, the distribution of negative samples plays a pivotal role in deriving the factorized matrix. In this work, we propose LocAPS (Loccal cluster-based Adaptive Positive Sampling), a novel sampling strategy that adaptively determines positive samples for each node based on local clustering. Building on LocAPS, we develop an enhanced NNE method, VERSE+, which achieves both sampling and training in linear time. For FNE, we introduce an adaptive negative sampling distribution derived from LocAPS, which tailors the sampling probability for each node. This distribution informs the construction of a factorized matrix that adaptively retains information from the similarity matrix. Moreover, its node-wise nature enables the development of FREDE+, an efficient streaming-style NE method with linear time and space complexity. We conduct extensive experiments on multiple real-world datasets, evaluating our methods on node classification and link prediction tasks, demonstrating their effectiveness and superior performance.

Attributed network embedding (ANE) can learn low-dimensional embeddings for nodes in attributed graphs, which can facilitate several data analysis tasks. However, the existing ANE methods fail to tackle scenarios involving the continuous generation of attributes. The ongoing generation of attributes accumulates numerous attributes, incurring high storage costs in existing methods. Furthermore, due to storage limitations, old attributes will be discarded as new ones are generated, existing methods struggle to integrate the new attribute information into embeddings generated from old attributes. Therefore, we propose a novel ANE framework named SANE (Streaming-style ANE), featuring a “memory” capability - that is, when updating the embeddings for new attributes, old attribute information can be partly preserved. In SANE, we first define forward and backward affinity between nodes and attributes by reviewing a node as source or target node. The definition guides quick computation of affinity vectors that integrate both topological and attribute information. Meanwhile, we propose an augmentation strategy to enrich node attribute information for enhance the quality of node embeddings. Leveraging the augmented attributes, we iteratively generate forward and backward affinity vectors, providing quantification of node-attribute affinity in two directions. Subsequently, we achieve a streaming-style update of node embeddings by employing matrix sketching technology on these iteratively generated vectors. Furthermore, capitalizing on the mergeability of matrix sketching, we efficiently integrate information of new generated attributes into node embeddings. Extensive experiments on 5 real datasets demonstrate that SANE surpasses the state-of-the-art algorithms in node classification and link prediction. SANE's ability to incorporate new attribute information into embeddings in a fast manner is validated through adequate simulation experiments.

Multimodal path queries over transportation networks are receiving increasing attention due to their widespread applications. A multimodal path query consists of finding multimodal journeys from source to destination in transportation networks, including unrestricted walking, driving, cycling, and schedule-based public transportation. Transportation networks are generally continent-sized. This characteristic highlights the need for parallel computing to accelerate multimodal path queries. Meanwhile, transportation networks are often fragmented and distributively stored on different machines. This situation calls for exploiting parallel computing power for these distributed systems. Therefore, in this paper, we studydistributed multimodal path (DMP) queriesover large transportation networks. We develop algorithms to explore parallel computation. When evaluating a DMP query$Q$on a distributed multimodal graph$Gmult$, we show that the algorithms possess the following performance guarantees, irrespective of how$Gmult$is fragmented and distributed: (1) each machine is visited only once; (2) the total network traffic is determined by the size of$Q$and the fragmentation of$Gmult$; (3) the response time is decided by the largest fragment of$Gmult$; and (4) the algorithm is parallel scalable. Using real-life and synthetic data, we experimentally verify that the algorithms are scalable on large graphs.

Graph queries have emerged as one of the fundamental techniques to support modern search services, such as PageRank web search, social networking search and knowledge graph search. As such graphs are maintained globally and very huge (e.g., billions of nodes), we need to efficiently process graph queries across multiple geographically distributed datacenters, running geo-distributed graph queries. Existing graph computing frameworks may not work well for geographically distributed datacenters, because they implement a Bulk Synchronous Parallel model that requires excessive inter-datacenter transfers, thereby introducing extremely large latency for query processing. In this paper, we propose GeoGraph --a universal framework to support efficient geo-distributed graph query processing based on clustering datacenters and meta-graph, while reducing the inter-datacenter communication. Our new framework can be applied to many types of graph algorithms without any modification. The framework is developed on the top of Apache Giraph. The experiments were conducted by applying four important graph queries, i.e., shortest path, graph keyword search, subgraph isomorphism and PageRank. The evaluation results show that our proposed framework can achieve up to 82% faster convergence, 42% lower WAN bandwidth usage, and 45% less total monetary cost for the four graph queries, with input graphs stored across ten geo-distributed datacenters.

Weight-constrained route planning (WRP) over static graphs has been extensively studied due to its wide application to transportation networks. However, real transportation networks often evolve over time and are thus modeled as time-dependent graphs. In this paper, we study the WRP problem over a large time-dependent graph by incorporating continuous time and weight functions into it. Most existing works regarding route planning over time-dependent graphs are based on the first-in-first-out (FIFO) property. Unfortunately, the FIFO property does not hold for our problem. To solve the problem, we propose two novel route planning algorithms, namely, a baseline algorithm and an advanced algorithm. Specifically, the advanced algorithm is even more efficient than the baseline algorithm, as the advanced algorithm incorporates a fast traversal scheme and tight bounds of time functions to terminate the traversal as early as possible. We confirm the effectiveness and efficiency of our algorithms by extensive experiments on real datasets.

Abstract A time-dependent graph is, informally speaking, a graph structure dynamically changes with time. In such graphs, the weights associated with edges dynamically change over time, that is, the edges in such graphs are activated by sequences of time-dependent elements. Many real-life scenarios can be better modeled by time-dependent graphs, such as bioinformatics networks, transportation networks, and social networks. In particular, the time-dependent graph is a very broad concept, which is reflected in the related research with many names, including temporal graphs, evolving graphs, time-varying graphs, historical graphs, and so on. Though static graphs have been extensively studied, for their time-dependent generalizations, we are still far from a complete and mature theory of models and algorithms. In this paper, we discuss the definition and topological structure of time-dependent graphs, as well as models for their relationship to dynamic systems. In addition, we review some classic problems on time-dependent graphs, e.g., route planning, social analysis, and subgraph problem (including matching and mining). We also introduce existing time-dependent systems and summarize their advantages and limitations. We try to keep the descriptions consistent as much as possible and we hope the survey can help practitioners to understand existing time-dependent techniques.

The constrained shortest path (CSP) query over static graphs has been extensively studied, since it has wide applications in transportation networks, telecommunication networks and etc. Such networks are dynamic and evolve over time, being modeled as time-dependent graphs. Therefore, in this paper, we study the CSP query over a large time-dependent graph. Specifically, we study the point CSP (PCSP) query and interval CSP (ICSP) query. We formally prove that it is NP-complete to process a PCSP query and at least EXPSPACE to answer an ICSP query. We propose approximate sequential algorithms to answer the PCSP and ICSP queries efficiently. We also develop parallel algorithms for the queries that guarantee to scale with big time-dependent graphs. Using real-life graphs, we experimentally verify the efficiency and scalability of our algorithms.