Complex Relational Community Search in Heterogeneous Information Networks

Scalable Exact Densest P-Partite Subgraph Search in Heterogeneous Information Networks

BoxDPpS performs box-level search with safe region pruning, eliminates redundant representations of the same iRM-set, improves early pruning through bounded warm-up, and compresses each fixed-M auxiliary network for exact parametric pseudoflow solving.

MonacGraph: A Monadic Second-Order Logic Extended Graph Database System with Community-Aware Storage

Graph database systems play a vital role in graph structure analysis across a wide range of application domains. Queries with set-level constraints on community structures are increasingly demanded in real-world applications. However, existing graph databases lack native support for both efficient monadic second-order logic (MSOL) query processing and fast community retrieval, hindering their applicability to such analytical tasks. In this paper, we present Monac- Graph, a graph database system that enables practical MSOL queries. MonacGraph features an efficient two-phase execution engine that minimizes redundant first-order clause evaluations. We propose SO-Gremlin, an extension of the Gremlin graph traversal language with intuitive syntax for set quantification. The system adopts LSM-Community as its storage backend, enabling efficient queries over precomputed graph structures. Additionally, MonacGraph provides a user-friendlyWeb interface for composing complex set-level queries and visualizing results in real time. A demonstration video can be found at https://www.youtube.com/watch?v=Eezdq9tzbJE.

Hierarchical heterogeneous information networks and approximate reduction under semantic controllability

The Hierarchical Heterogeneous Information Network is proposed as a data model that organizes typed entity relations in a main structure layer and descriptive evidence in a strong attribute layer as well as developing controllable approximate reduction as one instantiation.

Bridging Number and Magnitude in Heterogeneous Information Networks Similarity: A Convex Combination Approach over Arbitrary Meta-Paths

Heterogeneous information networks serve as one of the most important platforms in the fields of big data and artificial intelligence. Node similarity analysis is a fundamental yet crucial task. To explicitly distinguish the number of differing items and the total magnitude of interaction information between nodes of the same type under arbitrary meta-paths, while enabling flexible weighting between these two aspects, this paper proposes a similarity algorithm that formulates node similarity as a convex combination of vector norms. The proposed algorithm requires only the interaction information between typed nodes and does not depend on the type of metapath. It satisfies desirable properties including non-negativity, symmetry, self-maximum and boundedness. Experimental results on two real-world datasets demonstrate its superiority: on the Association for Computing Machinery Digital Library Dataset, the proposed algorithm achieves an average Silhouette of 0.67 on the paper-author-paper meta-path, outperforming PathSim and HeteSim by over 139%, and maintains a Calinski-Harabasz index approximately 6.6 times that of PathSim on the optimal paper-subject-paper meta-path. On the Internet Movie Database Dataset, it attains an average Silhouette of 0.77, which is 5.1 times and 3.0 times those of PathSim and HeteSim, respectively. Furthermore, the algorithm exhibits strong robustness, with minimal performance fluctuation across different meta-paths and clustering algorithms, whereas baseline methods suffer severe degradation. These results validate the efficiency and robustness of the proposed algorithm under various complex scenarios.

A Declarative Framework for Constrained Clique Detection in Heterogeneous Knowledge Graphs via ASP

Exploiting Structure in the Boolean Weighted Constraint Satisfaction Problem: A Constraint Composite Graph-Based Approach

What is"structure,"and how can we exploit it in combinatorial optimization? Reasoning tasks such as system design, state estimation, and prediction can be cast as combinatorial optimization problems (COPs), traditionally attacked by dedicated algorithms that fail outside their narrow subclass, while communities working on equivalent problems reinvent each other's techniques. The weighted constraint satisfaction problem (WCSP) is a general framework that subsumes COPs from many communities and represents complex physical and non-physical systems, from spin glasses to social networks. Is such generality a curse? Our answer is to exploit"structure": a general-purpose WCSP algorithm should automatically imitate the specialized algorithm for whatever subclass its input belongs to. A WCSP has macro (graphical) structure, which variables interact, and micro (numerical) structure, how they interact. Separate schools of thought exploit one or the other, never both. The constraint composite graph (CCG), introduced in 2008, unifies them: it is an undirected graph over a WCSP instance's variables plus auxiliary ones, on which minimum weighted vertex cover (MWVC) solves the original instance. It is efficiently constructible, but largely unexploited. This dissertation answers three questions affirmatively. The CCG has theoretical advantages beyond identifying tractable classes (new properties proved here); it is practically useful (efficient implementation and experiments); and it extends promisingly to non-Boolean variables (new encodings). We use the CCG to (a) kernelize a WCSP instance, fixing optimal values of some variables by maxflow before search begins, (b) improve min-sum message passing, (c) exploit integer linear programming solvers, and (d) solve COPs on quantum annealers. Solving general COPs faster classically also yields better baselines for the debated quantum advantage.