Active clustering enhances traditional semi-supervised clustering by introducing machine-led interaction, where informative constraints are dynamically selected and posed to humans. This enables goal-driven interaction and reduces the number of required constraints for achieving high-quality clustering. In this paper, we propose a newly designed Active Clustering framework with Minimal Constraint Graph (ACMCG). ACMCG operates on two cooperating tailored sparse graphs: a tree-structured graph (clustering tree) representing the nested clustering result, and a minimal constraint graph that supports constraint deduction during iterative refinement. In each refinement round, (a) the most suspicious edge in the tree is identified for constraint verification; (b) if a cannot-link constraint is confirmed, a pruning-and-grafting approach is performed to refine the clustering tree, guided by our proposed constraint deduction strategies; (c) the constraint is either deduced from the minimal constraint graph using transitive and probabilistic deduction, or obtained via user interaction when deduction fails. Extensive experiments across diverse domains demonstrate that ACMCG consistently outperforms both classical and state-of-the-art methods in accuracy, while significantly reducing the number of user-provided constraints and maintaining low computational cost, highlighting its cost-effectiveness in real-world applications.

Active constraint-based clustering enhances semi-supervised clustering through a machine-led interaction process. This approach dynamically selects the most informative constraints to query, minimizing the number of human annotations required. Existing methods face three key challenges in real-world applications: scalability, timeliness, and robustness against user annotation errors. In this work, we propose a robust and high-efficiency Active Clustering framework with Multi-user Collaboration (ACMC). ACMC constructs a diffusion tree using the nearest-neighbor technique and employs a multi-user online collaboration framework to iteratively refine clustering results. In each iteration: (a) nodes with high uncertainty and representativeness are selected in batch; (b) well-designed multi-user asynchronous query categorizes selected nodes using neighborhood sets, reducing individual workloads and improving overall timeliness; (c) user-provided constraints and newly discovered categories are synchronized, with user confidences dynamically updated to enhance robustness against erroneous annotations; (d) categorized nodes, stored in neighborhood sets, serve as sources in the diffusion tree to refine the clusters. Experimental results demonstrate that ACMC outperforms baseline methods in terms of clustering quality, scalability, and robustness against user annotation errors.

Clustering is inherently subjective: without additional guidance, it cannot independently determine the most appropriate grouping. This limitation underscores the necessity of active constrained clustering, which integrates user preferences (expressed as constraints) into the clustering process. However, existing methods of active constrained clustering encounter significant challenges when processing large-scale datasets, thereby restricting their practical application. To address this issue, we introduce Cluster Skeleton Exploration (CSE), a novel clustering method that effectively scales to large datasets while maintaining high clustering quality. In CSE, the dataset is represented as a cluster skeleton, a directed sparse graph. Each weakly connected component within this skeleton corresponds to a cluster. Through iterative constraint queries posed by the user, CSE dynamically refines the cluster skeleton until the desired clustering structure is achieved. CSE demonstrates exceptional scalability, significantly outperforming state-of-the-art methods. Extensive experiments conducted on diverse real-world datasets validate its superior clustering quality.

Clustering is fundamentally a subjective task: a single dataset can be validly clustered in various ways, and without further information, clustering systems cannot determine the appropriate clustering to perform. This underscores the importance of integrating constraints into clustering, enabling users to convey their preferences to the system. Active constraint-based clustering approaches prioritize the identification of the most valuable constraints to inquire about, striving to achieve effective clustering with the minimal number of constraints needed. We propose an A ctive C lustering with D iffusion M odel (ACDM). ACDM applies the nearest-neighbor technique to construct a diffusion graph, and utilizes an online framework to refine the clustering result iteratively. In each iteration, (a) nodes with high uncertainty and representativeness are selected in batch mode, (b) then a novel neighborhood-set-based query is used for categorizing the selected nodes, using pairwise constraints, and (c) the categorized nodes are used as source nodes in the diffusion model for cluster refinement. We experimentally demonstrate that ACDM outperforms state-of-the-art methods in terms of clustering quality and scalability.

Multi-label text classification (MLTC) is an important task in the field of natural language processing (NLP). Suffering from limited input length, most existing models learn text representation and label representation separately, leading to the overlook of correlations between texts and labels. To this end, we introduce a comprehensive model for the MLTC task. Under the same representation space, our model, which is equipped with Graph Convolutional Network (GCN) layer, attention mechanism, and contrastive learning objective, learns representations of texts and labels jointly. To tackle the issue caused by the input length limitation, we develop a two-stage label reduction method via the application of label merging and association. Our method’s effectiveness is validated through extensive experiments on various MLTC datasets, unraveling the intricate correlations between texts and labels.

As data dimensions and volume rapidly increase, attribute reduction using the original data becomes computationally infeasible. Large data frequently contain various redundant attributes and types of noise. This leads to the problems of overfitting and inefficiency in data processing. To address these problems, this paper proposes a general sampling method for attribute reduction by introducing three-way decisions, namely, three-way sampling (3WS), which is the first sampling method that describes the decision boundary accurately while improving the data quality significantly. To improve the effectiveness and efficiency of attribute reduction, we designed a rapid attribute reduction method based on three-way sampling (3WS-RAR). The 3WS-RAR method consists of three main steps: data sampling, attribute reduction, and model effectiveness evaluation. For data sampling, we define the three regions of the 3WS using support vectors to describe the data and use the boundary region as the sampling results. For the attribute reduction, we compute the neighborhood self-information for each attribute while considering the upper and lower approximations. For the effectiveness evaluation, we conducted experiments on 15 relatively large-scale datasets and analysed the influence of parameters. The experimental results reveal that, compared with state-of-the-art attribute reduction models, 3WS-RAR performs better on public benchmark datasets.

In the context of urbanization and the rapid growth of energy demand, understanding the spatial and temporal dynamics of urban energy use is crucial for identifying energy-saving potentials. In this demo, we present a visual analysis tool, VAP, that allows users to explore the dynamics of urban energy use at different spatial and temporal scales. In contrast to traditional statistical and machine learning methods, the visual analysis based tool focuses on analytical thinking, user interactions and answering business questions by examining different visual analysis views. In the demonstration, conference attendees will interact with VAP and learn its capabilities in discovering typical consumption patterns and spatio-temporal shift patterns from a real-world case study of electricity.

Answering queries using views has proven effective for querying relational and semistructured data. This paper investigates this issue for graph pattern queries based on graph simulation. We propose a notion ofpattern containmentto characterize graph pattern matching using graph pattern views. We show that a pattern query can be answered using a set of viewsif and only ifit is contained in the views. Based on this characterization, we develop efficient algorithms to answer graph pattern queries. We also study problems for determining (minimal, minimum) containment of pattern queries. We establish their complexity (from cubic-time to NP-complete) and provide efficient checking algorithms (approximation when the problem is intractable). In addition, when a pattern query is not contained in the views, we study maximally contained rewriting to find approximate answers; we show that it is in cubic-time to compute such rewriting, and present a rewriting algorithm. We experimentally verify that these methods are able to efficiently answer pattern queries on large real-world graphs.

We propose graph-pattern association rules (GPARs) for social media marketing. Extending association rules for item-sets, GPARs help us discover regularities between entities in social graphs, and identify potential customers by exploring social influence. We study the problem of discovering top- k diversified GPARs. While this problem is NP-hard, we develop a parallel algorithm with accuracy bound. We also study the problem of identifying potential customers with GPARs. While it is also NP-hard, we provide a parallel scalable algorithm that guarantees a polynomial speedup over sequential algorithms with the increase of processors. Using real-life and synthetic graphs, we experimentally verify the scalability and effectiveness of the algorithms.

Answering queries using views has proven an effective technique for querying relational and semistructured data. This paper investigates this issue for graph pattern queries based on (bounded) simulation, which have been increasingly used in, e.g., social network analysis. We propose a notion of pattern containment to characterize graph pattern matching using graph pattern views. We show that a graph pattern query can be answered using a set of views if and only if the query is contained in the views. Based on this characterization we develop efficient algorithms to answer graph pattern queries. In addition, we identify three problems associated with graph pattern containment. We show that these problems range from quadratic-time to NP-complete, and provide efficient algorithms for containment checking (approximation when the problem is intractable). Using real-life data and synthetic data, we experimentally verify that these methods are able to efficiently answer graph pattern queries on large social graphs, by using views.

This paper studies the problem of querying graphs within bounded resources. Given a query Q, a graph G and a small ratio α, it aims to answer Q in G by accessing only a fraction GQ of G of size |GQ| ≤ α |G|. The need for this is evident when G is big while our available resources are limited, as indicated by α. We propose resource-bounded query answering via a dynamic scheme that reduces big G to GQ. We investigate when we can find the exact answers Q(G) from GQ, and if GQ cannot accommodate enough information, how accurate the approximate answers Q(GQ) are. To verify the effectiveness of the approach, we study two types of queries. One consists of pattern queries that have data locality, such as subgraph isomorphism and strong simulation. The other is the class of reachability queries, without data locality. We show that it is hard to get resource-bounded algorithms with 100% accuracy: NP-hard for pattern queries, and non-existing for reachability when α ≠ 1. Despite these, we develop resource-bounded algorithms for answering these queries. Using real-life and synthetic data, we experimentally evaluate the performance of the algorithms. We find that they scale well for both types of queries, and our approximate answers are accurate, even 100% for small α.

This paper studies fundamental problems for distributed graph simulation. Given a pattern query Q and a graph G that is fragmented and distributed, a graph simulation algorithm A is to compute the matches Q ( G ) of Q in G . We say that A is parallel scalable in (a) response time if its parallel computational cost is determined by the largest fragment F m of G and the size | Q | of query Q , and (b) data shipment if its total amount of data shipped is determined by | Q | and the number of fragments of G, independent of the size of graph G . (1) We prove an impossibility theorem : there exists no distributed graph simulation algorithm that is parallel scalable in either response time or data shipment. (2) However, we show that distributed graph simulation is partition bounded, i.e. , its response time depends only on | Q |, | F m | and the number | V f | of nodes in G with edges across different fragments; and its data shipment depends on | Q | and the number | E f | of crossing edges only. We provide the first algorithms with these performance guarantees. (3) We also identify special cases of patterns and graphs when parallel scalability is possible. (4) We experimentally verify the scalability and efficiency of our algorithms.

We present ExpFinder, a system for finding experts in social networks based on graph pattern matching. We demonstrate (1) how ExpFinder identifies top-K experts in a social network by supporting bounded simulation of graph patterns, and by ranking the matches based on a metric for social impact; (2) how it copes with the sheer size of real-life social graphs by supporting incremental query evaluation and query preserving graph compression, and (3) how the GUI of ExpFinder interacts with users to help them construct queries and inspect matches.

Graph pattern matching has been widely used in e.g., social data analysis. A number of matching algorithms have been developed that, given a graph patternQand a graphG, compute the setM(Q,G)of matches ofQinG. However, these algorithms often return an excessive number of matches, and are expensive on large real-life social graphs. Moreover, in practice many social queries are to find matches of a specific pattern node, rather than the entireM(Q,G). This paper studies top-kgraph pattern matching. (1) We revise graph pattern matching defined in terms of simulation, by supporting a designated output nodeuo. GivenGandQ, it is to find those nodes inM(Q,G)that matchuo, instead of the large setM(Q,G). (2) We study two classes of functions for ranking the matches: relevance functions δr() based on, e.g., social impact, and distance functions δd() to cover diverse elements. (3) We develop two algorithms for computing top-kmatches ofuobased on δr(), with the early termination property, i.e., they find top-kmatches without computing the entireM(Q,G). (4) We also study diversified top-kmatching, a bi-criteria optimization problem based on both δr() and δd(). We show that its decision problem is NP-complete. Nonetheless, we provide an approximation algorithm with performance guarantees and a heuristic one with the early termination property. (5) Using real-life and synthetic data, we experimentally verify that our (diversified) top-kmatching algorithms are effective, and outperform traditional matching algorithms in efficiency.

It is common to find graphs with millions of nodes and billions of edges in, e.g., social networks. Queries on such graphs are often prohibitively expensive. These motivate us to propose query preserving graph compression, to compress graphs relative to a class Λ of queries of users' choice. We compute a small Gr from a graph G such that (a) for any query Q Ε Λ Q, Q(G) = Q'(Gr), where Q' Ε Λ can be efficiently computed from Q; and (b) any algorithm for computing Q(G) can be directly applied to evaluating Q' on Gr as is. That is, while we cannot lower the complexity of evaluating graph queries, we reduce data graphs while preserving the answers to all the queries in Λ. To verify the effectiveness of this approach, (1) we develop compression strategies for two classes of queries: reachability and graph pattern queries via (bounded) simulation. We show that graphs can be efficiently compressed via a reachability equivalence relation and graph bisimulation, respectively, while reserving query answers. (2) We provide techniques for aintaining compressed graph Gr in response to changes ΔG to the original graph G. We show that the incremental maintenance problems are unbounded for the two lasses of queries, i.e., their costs are not a function of the size of ΔG and changes in Gr. Nevertheless, we develop incremental algorithms that depend only on ΔG and Gr, independent of G, i.e., we do not have to decompress Gr to propagate the changes. (3) Using real-life data, we experimentally verify that our compression techniques could reduce graphs in average by 95% for reachability and 57% for graph pattern matching, and that our incremental maintenance algorithms are efficient.

In the real world a graph is often fragmented and distributed across different sites. This highlights the need for evaluating queries on distributed graphs. This paper proposes distributed evaluation algorithms for three classes of queries: reachability for determining whether one node can reach another, bounded reachability for deciding whether there exists a path of a bounded length between a pair of nodes, and regular reachability for checking whether there exists a path connecting two nodes such that the node labels on the path form a string in a given regular expression. We develop these algorithms based on partial evaluation , to explore parallel computation. When evaluating a query Q on a distributed graph G , we show that these algorithms possess the following performance guarantees, no matter how G is fragmented and distributed: (1) each site is visited only once ; (2) the total network traffic is determined by the size of Q and the fragmentation of G, independent of the size of G ; and (3) the response time is decided by the largest fragment of G rather than the entire G . In addition, we show that these algorithms can be readily implemented in the MapReduce framework. Using synthetic and real-life data, we experimentally verify that these algorithms are scalable on large graphs, regardless of how the graphs are distributed.

Graph pattern matching has become a routine process in emerging applications such as social networks. In practice a data graph is typically large, and is frequently updated with small changes. It is often prohibitively expensive to recompute matches from scratch via batch algorithms when the graph is updated. With this comes the need for incremental algorithms that compute changes to the matches in response to updates, to minimize unnecessary recomputation. This paper investigates incremental algorithms for graph pattern matching defined in terms of graph simulation, bounded simulation and subgraph isomorphism. (1) For simulation, we provide incremental algorithms for unit updates and certain graph patterns. These algorithms are optimal: in linear time in the size of the changes in the input and output, which characterizes the cost that is inherent to the problem itself. For general patterns we show that the incremental matching problem is unbounded, i.e., its cost is not determined by the size of the changes alone. (2) For bounded simulation, we show that the problem is unbounded even for unit updates and path patterns. (3) For subgraph isomorphism, we show that the problem is intractable and unbounded for unit updates and path patterns. (4) For multiple updates, we develop an incremental algorithm for each of simulation, bounded simulation and subgraph isomorphism. We experimentally verify that these incremental algorithms significantly outperform their batch counterparts in response to small changes, using real-life data and synthetic data.