Bipartite graphs are widely used to model relationships between entities of different types, where nodes are divided into two disjoint sets. Similarity search, a fundamental operation that retrieves nodes similar to a given query node, plays a crucial role in various real-world applications, including machine learning and graph clustering. However, existing state of-the-art methods often struggle to accurately capture the unique structural properties of bipartite graphs or fail to incorporate the informative node attributes, leading to suboptimal performance. Besides, their high computational complexity limits scalability, making them impractical for large graphs with millions of nodes and tens of thousands of attributes. To overcome these challenges, we first introduce Attribute-augmented Hidden Personalized PageRank (AHPP), a novel random walk model designed to blend seamlessly both the higher-order bipartite structure proximity and attribute similarity. We then formulate the similarity search over attributed bipartite graphs as an approximate AHPP problem and propose two efficient push-style local algorithms with provable approximation guarantees. Finally, extensive experiments on real-world and synthetic datasets validate the effectiveness of AHPP and the efficiency of our proposed algorithms when compared with fifteen competitors.

Abstract Symmetry, a phenomenon of self-similarity, is common in many networks, which often incurs a lot of redundant accesses and computations, even duplicate results when executing graph matching tasks. Many approaches (e.g. symmetry-breaking methods) try to disrupt symmetry by translating symmetry into restrictions and then imposing restrictions on the exploration order. However, the restrictions are finer-grained. If the pattern graph is complex, more restrictions are generated from symmetry breaking methods, thus complicating the exploration process and degrading the performance. Here, we present novel SymmPi, which exploits symmetry removal for fast graph matching. SymmPi first identifies the coarse-grained axisymmetric subgraphs of the given pattern graphs instead of finer relationships. If a pattern graph is not axisymmetric, SymmPi will remove some of its edges until axisymmetric subgraphs are found. Thus, the original pattern graph is transformed to a set of axisymmetric subgraphs plus some edges. Then, SymmPi finds the matches of the axisymmetric subgraph and extends these matches to the original pattern graphs by permuting the matches with additional checks. Our experiments on both directed and undirected graphs, demonstrate that SymmPi achieves a significant performance improvement over the state-of-the-art undirected and directed graph matching methods and systems.

Temporal community search is an important task in graph analysis, which has been widely used in many practical applications. However, existing methods suffer from two major defects: (i) they only require that the target result contains the query vertexq, leading to the temporal proximity betweenqand other vertices being ignored. Thus, they may find many temporal irrelevant vertices (these vertices are called query-drifted vertices) concerningqfor satisfying their objective functions; (ii) their methods are NP-hard, incurring high costs for exact solutions or compromised qualities for approximate/heuristic algorithms. In this paper, we propose a new problem named query-centered temporal community search to overcome these limitations. Specifically, we first present a novel concept of Time-Constrained Personalized PageRank to characterize the temporal proximity betweenqand other vertices. Then, we introduce a model calledβ-temporal proximity core, which can seamlessly combine temporal proximity and structural cohesiveness. Subsequently, our problem is formulated as an optimization task that finds aβ-temporal proximity core with the largestβ.We theoretically prove that our problem can circumvent these query-drifted vertices. To solve our problem, we first devise an exact and near-linear time greedy removing algorithm that iteratively removes unpromising vertices. To improve efficiency, we then design an approximate two-stage local search algorithm with bound-based pruning techniques. Finally, extensive experiments on eight real-life datasets and nine competitors show the superiority of the proposed solutions.

Learning Chinese word embeddings is important in many tasks of Chinese language information processing, such as entity linking, entity extraction, and knowledge graph. A Chinese word consists of Chinese characters, which can be decomposed into sub-characters (radical, component, stroke, etc). Similar to roots in English words, sub-characters also indicate the origins and basic semantics of Chinese characters. So, many researches follow the approaches designed for learning embeddings of English words to improve Chinese word embeddings. However, some Chinese characters sharing the same sub-characters have different meanings. Furthermore, with more cultural interaction and the popularization of the Internet and web, many neologisms, such as transliterated loanwords and network terms, are emerging, which are only close to the pronunciation of their characters, but far from their semantics. Here, a tripartite weighted graph is proposed to model the semantic relationship among words, characters, and sub-characters, in which the semantic relationship is evaluated according to the Chinese linguistic information. So, the semantic relevance hidden in lower components (sub-characters, characters) can be used to further distinguish the semantics of corresponding higher components (characters, words). Then, the tripartite weighted graph is fed into our Chinese word embedding modelinsideCC to reveal the semantic relationship among different language components, and learn the embeddings of words. Extensive experimental results on multiple corpora and datasets verify that our proposed methods outperform the state-of-the-art counterparts by a significant margin.

Abstract Now, with the prevalence of social media, such as Facebook, Weibo, how to maximize influence of individuals, products, actions in new media is of practical significance. Generally, maximizing influence first needs to identify the most influential individuals since they can spread their influence to most of others in the social media. Many studies on influence maximization aimed to select a subset of nodes in static graphs once. Actually, real graphs are evolving. So, influential individuals are also changing. In these scenarios, people tend to select influential individuals multiple times instead of once. Namely, selections are raised sequentially, forming a sequence (query sequence). It raises several new challenges due to changing influential individuals. In this paper, we explore the problem of Influence Maximization over Streaming Graph (SGIM). Then, we design a compact solution for storing and indexing streaming graphs and influential nodes that eliminates the redundant computation. The solution includes Influence-Increment-Index along with two sketch-centralized indices called Influence-Index and Reverse-Influence-Index. Computing influence set of nodes will incur a large number of redundant computations. So, these indices are designed to keep track of the nodes’ influence in sketches. Finally, with the indexing scheme, we present the algorithm to answer SGIM queries. Extensive experiments on several real-world datasets demonstrate that our method is competitive in terms of both efficiency and effectiveness owing to the design of index.

Reachability query asks whether a vertex can reach another vertex on large directed graphs. It is one of the most fundamental graph operators and has attracted many researchers to study it. Although there are many approaches solving this problem, it still remains a challenging problem when it comes to leverage the three main costs: the index construction time, the index size, and the query time on large and dense graphs. In this paper, we propose a High Dimension Graph Labeling approach to answer reachability queries. First, we recursively partition a graph into disjoint non-shared graphs, among which there are no common vertices, and cross edges. Second, we build a four dimensional label - one dimension of layer, one dimension of sub-graph and two dimensions of interval for each vertex. With the layer label and the sub-graph label, we can determine the positions (non-shared graphs) of any two vertices. Two dimensional interval label is used to assist to answer the reachability queries for vertex pair in those non-shared graphs. Finally, we design algorithms to answer researchability queries efficiently. In order to speed up query answering, we also build two directional labels: up and down labels to filter vertices quickly. The extensive experiments on 28 large/small and dense/sparse graphs show that building the high dimensional index is quickly and the index size is also competitive compared with most of the state of the art approaches. The results also show that our approach is more scalable and efficient than the state-of-the-art approaches in answering reachability queries.

The emerging need for conducting complex analysis over big RDF datasets calls for scale-out solutions that can harness a computing cluster to process big RDF datasets. Queries over RDF data often involve complex self-joins, which would be very expensive to run if the data are not carefully partitioned across the cluster and hence distributed joins over massive amount of data are necessary. Existing RDF data partitioning methods can nicely localize simple queries but still need to resort to expensive distributed joins for more complex queries. In this paper, we propose a new data partitioning approach that takes use of the rich structural information in RDF datasets and minimizes the amount of data that have to be joined across different computing nodes. We conduct an extensive experimental study using two popular RDF benchmark data and one real RDF dataset that contain up to billions of RDF triples. The results indicate that our approach can produce a balanced and low redundant data partitioning scheme that can avoid or largely reduce the cost of distributed joins even for very complicated queries. In terms of query execution time, our approach can outperform the state-of-the-art methods by orders of magnitude.

Now more and more large graphs are available. One interesting problem is how to effectively find reachability between any vertex pairs in a very large graph. Multiple approaches have been proposed to answer reachability queries. However, most approaches only perform well on small graphs. Processing reachability queries on large graphs requires much storage and computation and still remains challenges. In this paper, we propose a scalable and fast indexing approach called Interval-Index, based on traversal tree-based partitioning and relabeling scheme. Our approach has several unique features: first, the traversal tree-based partitioning ensures access locality and parallelism in computation; second, continuous relabeling ensures fast querying and saves search space; third, we convert the entire graph database into a traversal tree graph on a smaller scale, to reach a compact storage structure. Finally, we run extensive experiments on synthetic graphs and real graphs with different sizes, and show that Interval-Index approach outperforms the state-of-the-art Feline in both storage size and the performance of query execution.

The flexibility of the RDF data model has attracted an increasing number of organizations to store their data in an RDF format. With the rapid growth of RDF datasets, we envision that it is inevitable to deploy a cluster of computing nodes to process large-scale RDF data in order to deliver desirable query performance. In this paper, we address the challenging problems of data partitioning and query optimization in a scale-out RDF engine. We identify that existing approaches only focus on using fine-grained structural information for data partitioning, and hence fail to localize many types of complex queries. We then propose a radically different approach, where a coarse-grained structure, namely Rooted Sub-Graph (RSG), is used as the partition unit. By doing so, we can capture structural information at a much greater scale and hence are able to localize many complex queries. We also propose a k-means partitioning algorithm for allocating the RSGs onto the computing nodes as well as a query optimization strategy to minimize the inter-node communication during query processing. An extensive experimental study using benchmark datasets and real dataset shows that our engine, SemStore, outperforms existing systems by orders of magnitudes in terms of query response time.

The volume of RDF data continues to grow over the past decade and many known RDF datasets have billions of triples. A grant challenge of managing this huge RDF data is how to access this big RDF data efficiently. A popular approach to addressing the problem is to build a full set of permutations of (S, P, O) indexes. Although this approach has shown to accelerate joins by orders of magnitude, the large space overhead limits the scalability of this approach and makes it heavyweight. In this paper, we present TripleBit, a fast and compact system for storing and accessing RDF data. The design of TripleBit has three salient features. First, the compact design of TripleBit reduces both the size of stored RDF data and the size of its indexes. Second, TripleBit introduces two auxiliary index structures, ID-Chunk bit matrix and ID-Predicate bit matrix, to minimize the cost of index selection during query evaluation. Third, its query processor dynamically generates an optimal execution ordering for join queries, leading to fast query execution and effective reduction on the size of intermediate results. Our experiments show that TripleBit outperforms RDF-3X, MonetDB, BitMat on LUBM, UniProt and BTC 2012 benchmark queries and it offers orders of mangnitude performance improvement for some complex join queries.