Subgraph matching (SM) is a fundamental problem in graph data analysis. Real-world patterns used in graph analysis are often symmetric and contain isomorphic substructures, but existing SM algorithms fail to explore such properties. To fill this gap, we propose MuSha, a multi-objective optimization framework for SM, leveraging multilevel sharing of isomorphic substructure results to speed up SM and symmetry breaking to avoid directly computing symmetric results. To efficiently compute and cache intermediate results for sharing, MuSha applies worst-case optimal joins (WCOJs) and utilizes trie data structures to compress and index results. To enable multilevel sharing, MuSha solves a multi-objective optimization problem involving pattern decomposition, symmetry breaking, WCOJ orders, and trie structural orders. Experimental results demonstrate that MuSha outperforms the state of the art by up to two orders of magnitude on graphs of millions of vertices.

The subgraph matching problem is crucial in graph analysis, involving identifying all instances of a given pattern$P$within a graph$G$. Advances in this field aim to uncover larger patterns across diverse graph types and subgraph matching tasks. However, existing methods often prove inefficient for such tasks. To address this gap, we propose CSCE, which generates efficient plans for various problem settings. CSCE utilizes clustered compressed sparse rows for heterogeneous graphs and sequential candidate equivalence to reduce redundant computations. Moreover, our approach seamlessly supports different subgraph matching variants, such as edge-induced, vertex-induced, and homomorphic scenarios. Experiments show that our work is up to two orders of magnitude faster than the state of the art on graphs of millions scale.

While motif has been widely employed in graph analytics, a fundamental question remains open: How should overlapping motif edges connect into a path? Existing works address this question with simple but inconsistent generalizations from standard graphs. This paper studies this issue by proposing the concept of connectivity degree (CD), i.e. the number of overlapping nodes needed for motif edges to be adjacent, as the requirement for path connection. We further study three research questions. First, is CD significant? We study how CD impacts motif analytics, more specifically, three motif-based methods. Second, how to estimate the right CD? We develop a minimax estimator based on minimizing the worst-case risk. Finally, how to detect the connected components with connectivity degree, an important task by itself and necessary for our estimator. As the traditional BFS or DFS approaches are not valid anymore, we develop a disjoint set algorithm instead. Our experiments validate that our CD can improve the performance of motif analytics. Also, our estimator is effective and our connected component detection algorithm is efficient.

SimRank is a popular link-based similarity measure on graphs. It enables a variety of applications with different modes of querying (e.g., single-pair, single-source and all-pair modes). In this paper, we propose UISim, a unified and incremental framework for all SimRank modes based on a scheduled approximation principle. UISim processes queries with incremental and prioritized exploration of the entire computation space, and thus allows flexible tradeoff of time and accuracy. On the other hand, it creates and shares common building blocks for online computation without relying on indexes, and thus is efficient to handle both static and dynamic graphs. Our experiments on various real-world graphs show that to achieve the same accuracy, UISim runs faster than its respective state-of-the-art baselines in each mode, and scales well on larger graphs.

SimRank is a popular link-based similarity measure on graphs. It enables a variety of applications with different modes of querying. In this paper, we propose UISim, a unified and incremental framework for all SimRank modes based on a scheduled approximation principle. UISim processes queries with incremental and prioritized exploration of the entire computation space, and thus allows flexible tradeoff of time and accuracy. On the other hand, it creates and shares common “building blocks” for online computation without relying on indexes, and thus is efficient to handle both static and dynamic graphs. Our experiments on various real-world graphs show that to achieve the same accuracy, UISim runs faster than its respective state-of-the-art baselines, and scales well on larger graphs.

Path-based solutions have been shown to be useful for various graph analysis tasks, such as link prediction and graph clustering. However, they are no longer adequate for handling complex and gigantic graphs. Recently, motif-based analysis has attracted a lot of attention. A motif, or a small graph with a few nodes, is often considered as a fundamental unit of a graph. Motif-based analysis captures high-order structure between nodes, and performs better than traditional "edge-based" solutions. In this paper, we study motif-path , which is conceptually a concatenation of one or more motif instances. We examine how motif-paths can be used in three path-based mining tasks, namely link prediction, local graph clustering and node ranking. We further address the situation when two graph nodes are not connected through a motif-path, and develop a novel defragmentation method to enhance it. Experimental results on real graph datasets demonstrate the use of motif-paths and defragmentation techniques improves graph analysis effectiveness.

Graph databases witness the rise of Graph Query Language (GQL) in recent years, which enables non-programmers to express a graph query. However, the current solution does not support motif-related queries on knowledge graphs, which are proven important in many real-world scenarios. In this paper, we propose a GQL framework for mining knowledge graphs, named M-Cypher. It supports motif-related graph queries in an effective, efficient and user-friendly manner. We demonstrate the usage of the system by the emerging Covid-19 knowledge graph analytic tasks.

With the rapid improvement of various techniques in graph-based semi-supervised learning, the call for higher-quality graphs becomes more intensive. However, such affinity graphs are not naturally existing in most semi-supervised learning tasks. In this paper, we propose a learning-based approach, GraphEBM, for the graph construction problem. GraphEBM is designed to address three main requirements in graph construction: 1) supporting dynamic update; 2) providing interpretable metrics; 3) tailoring to tasks. Specifically, in GraphEBM, we adopt a probabilistic view, Edge Probability Space, to model a graph construction process as constituted of events from the space. Our objective is thus to learn, by our Energy-Based Model (EBM), the latent sampling distribution. Experimental results show that our proposed GraphEBM outperforms the existing graph construction methods in improving the semi-supervised learning tasks on various datasets and it can learn global properties of a target graph only with direct local guidance.