Role-playing capabilities in large language models (LLMs) often lack cognitive consistency in complex scenarios that require deep understanding and coherent reasoning.While recent reasoning models excel in math and coding tasks, they show limited effectiveness in open-ended role-playing scenarios.We introduce R-CHAR (Role-Consistent Hierarchical Adaptive Reasoning), a metacognition-driven framework that enhances role-playing performance through guided thinking trajectories synthesis and adaptive evaluation.Our approach demonstrates that concise thinking processes can achieve superior performance efficiently compared to elaborate reasoning chains in roleplaying social intelligence tasks, outperforming existing specialized models.Experimental results on the SocialBench benchmark show significant and stable performance improvements across varying scenario complexities, showing particular strength in long-context comprehension (from 34.64% to 68.59%) and grouplevel social interactions.Our work advances the development of cognitively consistent roleplaying systems, bridging the gap between surface-level mimicry and authentic character simulation.

Recently, graph matching has become a fundamental tool in various fields of computer science due to its ability to accurately capture node correspondences between graphs. Among these, multi-graph matching, as an emerging challenge, has achieved superior global information fusion compared to two-graph matching under the principle of cycle consistency. However, existing SOTA methods do not consider scenarios involving multi-cluster mixed graphs, instead assuming that all graphs originate from the same cluster. This assumption is overly idealistic, and the corresponding algorithms are easier to implement. A previous study attempted to address this issue, but its method sacrificed cycle consistency and failed to naturally integrate clustering into the algorithm. To address this, we propose a novel method based on the maximum entropy model, transforming the clustering problem into a binary classification problem for pairwise matching and incorporating the classification results as probabilistic factors into the objective function, achieving a natural combination of clustering and cycle consistency. Furthermore, we introduce spatial consistency, enabling the model to exhibit better robustness in scenarios such as annotation shifts. Experimental results demonstrate that our method outperforms existing SOTA methods in both matching accuracy and clustering effectiveness, while also achieving competitive time cost.

Graph matching (GM) aims to find the optimal node correspondence between graphs, and its challenges are further reflected in partial matching scenarios with outliers, which are widely present due to (self-)occlusion of objects or annotation errors. In this paper, we extend this challenge to visual scenes containing redundant points outside the objects. However, SOTA GM methods are not well-suited for such scenarios. They introduce virtual nodes to tolerate the presence of outliers or add a learning-constrained plugin after the matching solver to select the top-k matching pairs. The issue with these methods is that they allow outliers to participate in model learning, leading to incorrect matches. To address this, we designed a pre-processing plugin applicable to all models for pre-filtering outliers, which, from the user’s perspective, is simply a node editing task. We further designed an inductive solver and employed a hashing method to measure graph embedding similarity, thereby improving model accuracy and scalability. Most critically, we constructed the GM pipeline based on edge-free graphs, which is fundamentally different from traditional methods that add virtual edges to nodes. Experimental results demonstrate that our model outperforms SOTA GM methods in terms of matching accuracy, scalability, and robustness.

Spatial tensors have been extensively used in a wide range of applications, including remote sensing, geospatial information systems, conservation planning, and urban planning. We study the problem of Spatially Compact Dense (SCD) block mining in a spatial tensor, which targets for discovering dense blocks that cover small spatial regions. However, most of existing dense block mining (DBM) algorithms cannot solve the SCD-block mining problem since they only focus on maximizing the density of candidate blocks, so that the discovered blocks are spatially loose, i.e., covering large spatial regions. Therefore, we first formulate the problem of mining top-k Spatially Compact Dense blocks (SCD-blocks) in spatial tensors, which ranks SCD-blocks based on a new scoring function that takes both the density value and the spatial coverage into account. Then, we adopt a filter-refinement framework that first generates candidate SCD-blocks with good scores in the filtering phase and then uses the traditional DBM algorithm to further maximize the density values of the candidates in the refinement phase. Due to the NP-hardness of the problem, we develop two types of solutions in the filtering phase, namely the top-down solution and the bottom-up solution, which can find good candidate SCD-blocks by approximately solving the new scoring function. The evaluations on four real datasets verify that compared with the dense blocks returned by existing DBM algorithms, the proposed solutions are able to find SCD-blocks with comparable density values and significantly smaller spatial coverage.

Network connectivity minimization is a fundamental problem in controlling the spread of viruses in the Internet and facilitating information propagation in online social networks. The problem aims to identify a budget number of key nodes whose removal would minimize the connectivity of a network. However, the existing solutions heavily rely on the number of edges, making it challenging to handle large and densely connected social networks. In this study, we present a fast algorithm that is independent of the number of edges. To achieve this, we first introduce a surrogate matrix that approximates the residual adjacency matrix with arbitrary small predefined error. We then devise an efficient approach for inferring k influential nodes by optimizing the eigenvalues of the surrogate matrix. Remarkably, the algorithm has a small time complexity of O(knr3), with r being a small tunable number. Our algorithm thereby maintains a linear scalability in terms of the number of nodes and is unaffected by the number of edges. Hence, it has the capability to efficiently handle large and dense social networks. At last, we evaluate its performance against state-of-the-art techniques using diverse real-world datasets. The experimental results demonstrate the superiority of our proposed method in terms of both solution quality and computational efficiency.

The number of triangles of a streaming graph is a crucial metric with various applications, such as network evolution analysis, community detection, and anomaly detection. A practical solution for triangle counting in streaming graphs is the sampling-based approximation. Although a lot of research efforts have been devoted to the fixed-sized memory based algorithms, they suffer from the accuracy and the efficiency issues. To tackle these issues, we first propose the generalized reservoir sampling (GRS), which stores less edges for reducing the computational cost and can still generate uniformly random edge sample in the streaming graph. Then, we propose the GREAT algorithm based on GRS for efficient and accurate triangle counting estimation. To further improve the estimation accuracy, we propose the GREAT + algorithm for considering the dynamic timestamp interval distribution in real-world streaming graphs so that triangles with short and long timestamp intervals will be sampled following the ground-truth distribution. Extensive evaluations on real datasets demonstrate the efficiency and the accuracy of our algorithms. The relative error of our algorithm GREAT + is significantly (an order of magnitude) better than the competitors.

Explainable recommender systems ( ERS ) aim to enhance users’ trust in the systems by offering personalized recommendations with transparent explanations. This transparency provides users with a clear understanding of the rationale behind the recommendations, fostering a sense of confidence and reliability in the system’s outputs. Generally, the explanations are presented in a familiar and intuitive way, which is in the form of natural language, thus enhancing their accessibility to users. Recently, there has been an increasing focus on leveraging reviews as a valuable source of rich information in both modeling user-item preferences and generating textual interpretations, which can be performed simultaneously in a multi-task framework. Despite the progress made in these review-based recommendation systems, the integration of implicit feedback derived from user-item interactions and user-written text reviews has yet to be fully explored. To fill this gap, we propose a model named SERMON (A s pect-enhanced E xplainable R ecommendation with M ulti-modal C o ntrast Lear n ing). Our model explores the application of multimodal contrastive learning to facilitate reciprocal learning across two modalities, thereby enhancing the modeling of user preferences. Moreover, our model incorporates the aspect information extracted from the review, which provides two significant enhancements to our tasks. Firstly, the quality of the generated explanations is improved by incorporating the aspect characteristics into the explanations generated by a pre-trained model with controlled textual generation ability. Secondly, the commonly used user-item interactions are transformed into user-item-aspect interactions, which we refer to as interaction triple, resulting in a more nuanced representation of user preference. To validate the effectiveness of our model, we conduct extensive experiments on three real-world datasets. The experimental results show that our model outperforms state-of-the-art baselines, with a 2.0% improvement in prediction accuracy and a substantial 24.5% enhancement in explanation quality for the TripAdvisor dataset.

Graph partitioning is of great importance to optimizing the performance and cost of geo-distributed graph analytics applications. However, it is non-trivial to obtain efficient and effective partitioning due to the challenges brought by thelarge graph scales,dynamic graph changesand thenetwork heterogeneityin geo-distributed data centers (DCs). Existing studies usually adopt heuristic-based methods to achieve fast and balanced partitioning for large graphs, which are not powerful enough to address the complexity in our problem. Further, graph structures of many applications can change at various frequencies. Dynamic partitioning methods usually focus on achieving low latency to quickly adapt to changes, which unfortunately sacrifices partitioning effectiveness. Also, such methods are not aware of the dynamicity of graphs and can over sacrifice effectiveness for unnecessarily low latency. To address the limitations of existing studies, we proposeDistRLCut, a novel graph partitioner which leverages Multi-Agent Reinforcement Learning (MARL) to solve the complexity of the partitioning problem. To achieve fast partitioning for large graphs,DistRLCutadapts MARL to a distributed implementation which significantly accelerates the learning process. Further,DistRLCutincorporates two techniques to trade-off between partitioning effectiveness and efficiency, including local training and agent sampling. By adaptively tuning the number of local training iterations and the agent sampling rate,DistRLCutis able to achieve good partitioning results within an overhead constraint required by graph dynamicity. Experiments using real cloud DCs and real-world graphs show that, compared to state-of-the-art static partitioning methods,DistRLCutimproves the performance of geo-distributed graph analytics by 11%-95%.DistRLCutcan partition over 28 million edges per second, showcasing its scalability for large graphs. With varying graph changing frequencies,DistRLCutcan improve the performance by up to 71% compared to state-of-the-art dynamic partitioning.

Extreme learning machines (ELM) has been widely used in data stream processing, but because the parameters of ELM are generated randomly, the general approximation ability of randomized neural network depends on hidden layer nodes and random parameter range, if the parameters are improperly set, the objective function can not be approximated with high probability. Stochastic Configuration Network(SCN) solves this problem. In order to deal with the problem of data stream classification better, this paper proposes SSOE-FW-SCN, which combines the advantages of SCN and online elastic ELM. The algorithm adds class weights in the initialization phase and online update phase to adapt to the problem of class imbalance. The confusion matrix is used to dynamically calculate the class weight and forgetting factor, which makes the algorithm adapt to the problem of concept drift and class imbalance. In addition to parameter update, the algorithm also adds semi-supervised structure update in the online phase, which makes the algorithm adapt to more concept drift scenarios and class imbalance problems. Compared with the existing data stream classification algorithms, the proposed algorithm has better approximation and robustness.

Blockchain technology has garnered increasing attention from researchers. Because blockchain systems may contain malicious or spatially limited nodes that may delay block verification and reduce block transmission rate, this work proposes a block transmission model by designing and using special clusters. This work proposes the cluster formation and selection mechanisms. Nodes are grouped into clusters in a blockchain, and clusters with high fitness values are chosen to transmit blocks by calculating their trust values and block transmission rates. The proposed method is compared with the peers: Layer-Chain, BlockP2P-EP and RNS. According to experimental findings, the proposed method is superior to its peers regarding the time needed for block synchronization and transmission, block occupation storage ratio, transaction throughput, and block transmission success ratio.

Federated learning enables collaborative AI training across organizations without compromising data privacy. Decentralized federated learning (DFL) improves this by offering enhanced reliability and security through peer-to-peer (P2P) model sharing. However, DFL faces challenges in terms of slow convergence rate due to complex P2P graphs. To address this issue, we propose an efficient algorithm to accelerate DFL by introducing a limited number of k of edges into the P2P graphs. Specifically, we establish a connection between the convergence rate and the second smallest eigenvalue of the laplacian matrix of the P2P graph. We prove that finding the optimal set of edges to maximize this eigenvalue is an NP-complete problem. Our quantitative analysis shows the positive effect of strategic edge additions on improving this eigenvalue. Based on the analysis, we then propose an efficient algorithm to compute the best set of candidate edges to maximize the second smallest eigenvalue, and consequently the convergence rate is maximized. Our algorithm has a low time complexity of O(krn^2). Experimental results on diverse datasets validate the effectiveness of our proposed algorithms in accelerating DFL convergence.

PageRank is a commonly used measurement in a wide range of applications, including search engines, recommendation systems, and social networks. However, this measurement suffers from huge computational overhead, which cannot be scaled to large graphs. Although many approximate algorithms have been proposed for computing PageRank values, these algorithms are either (i) not efficient or (ii) not accurate. Worse still, some of them cannot provide estimated PageRank values for all the vertices. In this paper, we first propose the CUR-Trans algorithm, which can reduce the time complexity for computing PageRank values and has lower error bound than existing matrix approximation-based PageRank algorithms. Then, we develop the T 2 -Approx algorithm to further reduce the time complexity for computing this measurement. Experiment results on three large-scale graphs show that both the CUR-Trans algorithm and the T 2 -Approx algorithm achieve the lowest response time for computing PageRank values with the best accuracy (for the CUR-Trans algorithm) or the competitive accuracy (for the T 2 -Approx algorithm). Besides, the two proposed algorithms are able to provide estimated PageRank values for all the vertices.

Attributed graphs are graphs, where the vertices have attributes. Such graphs encompass, e.g., social network graph, citation graphs, and knowledge graphs, which have numerous real-world applications. Keyword-based search is a prominent and user-friendly way of querying attributed graphs. One widely used approach to keyword search adopts tree-based query semantics that relies on scoring functions that aggregate distances from a root to keyword-matched vertices. However, it is non-trivial to design scoring functions that capture different users’ keyword preferences. This study defines and solves the skyline KTree retrieval problem that combines keyword querying with skyline functionality on attributed graphs. The result of a skyline KTree query is independent of scoring functions. Hence, no matter which keywords are preferred, users can always find their favorite KTrees in a result. To enable efficient skyline KTree retrieval, we propose algorithm$\mathsf {FilterRefine}$that first identifies candidate results and then uses them for search space pruning. Computing distances between keywords and vertices is expensive and dominates the computational cost of$\mathsf {FilterRefine}$. Inspired by subspace skyline query techniques, we convert the skyline KTree retrieval problem into a multi-dimensional subspace skyline problem and propose algorithm$\mathsf {MultiDiSkylineOpt}$. This algorithm is able to reuse skylines in subspaces and uses bounds on all dimensions to accelerate distance computation. Experimental results on real datasets show that a baseline algorithm cannot report results within a 500 second cut-off time, while the proposed algorithms are able to compute results in reasonable time. In particular,$\mathsf {MultiDiSkylineOpt}$is able to efficiently retrieve skyline KTrees on large graphs with millions of nodes and hundreds of millions of edges.

Hao Cheng, Shuo Wang, Wensheng Lu, Wei Zhang, Mingyang Zhou, Kezhong Lu, Hao Liao. Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2023.

Attributed graph clustering aims to partition the nodes in a graph into groups such that the nodes in the same group are close in terms of graph proximity and also have similar attribute values. Recently, deep learning methods have achieved state-of-the-art clustering performance. However, the effectiveness of existing methods remains unclear due to two reasons. First, the datasets used for evaluation do not support fully the goal of attributed graph clustering. The category labels of nodes are only relevant to node attributes, and nodes with the same category label are often distant in the graph. Second, existing methods for the attributed graph clustering are complex and consist of several components. There is lack of comparisons of methods composed of different components from existing methods. This study proposes six benchmark datasets that support better the goal of attributed graph clustering and reports the performance of existing representative methods. Given that existing methods leave room for improvement on the proposed benchmark datasets, we systematically analyze five aspects of existing methods: encoded information, training networks, fusion mechanisms, loss functions, and clustering result generation. Based on these aspects, we decompose existing methods into modules and evaluate the performance of reconfigured methods based on these modules. According to the experimental results on the proposed benchmark datasets, we identify two promising configurations: (i) taking the attribute matrix as input to a graph convolutional network and (ii) layer-wise linear fusing deep neural network and graph attention network. And we also find that complex loss function fails to improve the clustering performance.

The proliferation of event-based social networking (EBSN) motivates studies on topics such as event, venue, and friend recommendation as well as event creation and organization. In this setting, the notion of event-partner recommendation has attracted attention. When recommending an event to a user, this functionality allows the recommendation of partners with whom to attend the event. However, in existing proposals, recommendations are pushed to users at the system's initiative. In contrast, EBSNs provide users with keyword-based search functionality. This way, users may retrieve information in pull mode. We propose a new way of accessing information in EBSNs that combines pull and push, thus allowing users to not only conduct ad-hoc searches for events, but also to receive partner recommendations for retrieved events. Specifically, we define and study top-k k event-partner (k kEP) pair retrieval querying that integrates keyword-based search for events with event-partner recommendation. This type of query retrieves event-partner pairs, taking into account the relevance of events to user-supplied keywords and so-called together preferences that indicate the extent of a user's preference to attend an event with a given partner. To compute k kEP queries efficiently, we propose a rank-join based framework with three optimizations. Results of empirical studies with implementations of the proposed techniques demonstrate that the proposed techniques are capable of excellent performance.

Flow prediction attracts intensive research interests, since it can offer essential support to many crucial problems in public safety and smart city, e.g., epidemic spread prediction and medical resource allocation optimization. Among all the models in flow prediction, deep learning models (e.g., convolutional neural networks, recurrent neural networks, and graph neural networks) are popular and outperform other statistics and machine learning models, since they can learn intrinsic structures and extract features from spatial–temporal (ST) data. However, most of them set strict temporal periods in the prediction or separate the interaction between spatial and temporal correlations. Therefore, the prediction accuracy is affected. To overcome the difficulties, we propose a flow prediction network attentive spatial–temporal convolutional network (ASTCN), which can effectively handle large-scale flow data and learn complex features. In ASTCN, we leverage an attention mechanism to overcome the previous problem of strict temporal periods, and can effectively fuse ST data with multiple factors from different time-series sources. Furthermore, we propose a causal 3-D convolutional layer based on temporal convolutional networks (TCNs). It can simultaneously extract both spatial and temporal features to improve the prediction accuracy. We comprehensively conducted our experiments based on real-world data sets. Experimental results show that ASTCN outperforms the state-of-the-art methods by at least 3.78% in root mean square error. Therefore, ASTCN is a potential solution to other large-scale ST problems.

So-called spatial web queries retrieve web content representing points of interest, such that the points of interest have descriptions that are relevant to query keywords and are located close to a query location. Two broad categories of such queries exist. The first encompasses queries that retrieve single spatial web objects that each satisfy the query arguments. Most proposals belong to this category. The second category, to which this paper's proposal belongs, encompasses queries that support exploratory user behavior and retrieve sets of objects that represent regions of space that may be of interest to the user. Specifically, the paper proposes a new type of query, the top-$k$spatial textual cluster retrieval ($k$-STC) query that returns the top-$k$clusters that (i) are located close to a query location, (ii) contain objects that are relevant with regard to given query keywords, and (iii) have an object density that exceeds a given threshold. To compute this query, we propose a DBSCAN-based approach and an OPTICS-based approach that rely on on-line density-based clustering and that exploit early stop conditions. Empirical studies on real data sets offer evidence that the paper's proposals can find good quality clusters and are capable of excellent performance.

In wireless sensor networks, sensor nodes collect data from the surrounding environment and transfer it to the base station. If a sensor node cannot communicate with the base station directly, it needs to select one of the senor nodes that it can communicate with and transfer the data to it. The above process will go on until the data arrive at the base station. It may cause too many relays during the process in which the data are transferred to the base station. Some nodes may quickly run out of energy and cause the entire wireless network to fail. We build a breadth-first search spanning tree which is rooted in base station according to the connected relation between the sensor nodes and the base station. When sensor nodes transfer the data to the base station, the data follow the path between the node and root in the spanning tree towards the base station. This algorithm guarantees the number of relays in the process and the total energy consumption of the wireless sensor network are the least. Thus the choice of the base station position is vital to the energy consumption of the whole wireless sensor network. This paper proposes an algorithm for the base station placement that finds the optimal base station position by using computation geometry according to the relative relation between the senor nodes. In contrast to the grid computing we are familiar, this algorithm greatly reduces the computing time required by finding the optimal position of base station.

The FP-tree based edge weight computation (EWC for short) with MapReduce has demonstrated its remarkable performance for extracting weighted graphs from big data for data analysis. However, our investigation finds that existing algorithm includes unnecessary scan on the datasets as well as unnecessary information for the FP-tree construction, which prolong the runtime execution. In addition, applying inappropriate Reducers-to-cores mapping strategy may make it exhaust the resources and fail to complete the job execution. This paper designs, implements and evaluates an optimized FP-tree based graph EWC algorithm with MapReduce on Multi-core Clusters. First, we design a more compact FP-tree based EWC with 2-phase MapReduce, reducing one phase scan of the dataset. Second, we propose a reduced FP-tree data structure to reduce the FP-tree construction cost. Third, we examine two strategies for mapping Reducers to cores for EWC on each multi-core computer: {\em one-Reducer-one-core} and {\em one-Reducer-multiple-cores}. Finally, an empirical comparison performance study has been carried out on the optimized EWC algorithm against the existing one over a massive application dataset generated by a real social network. The results demonstrate that the optimized FP-tree based EWC algorithm obtains about 39\% to 55\% percentage improvement in execution time, and in the meantime achieves better scale-out and scale-up speedup. This paper's findings can also be applied to improve the scalability and efficiency of the parallel and distributed execution of applications involving large scale all-pairs set intersection computation over multi-core MapReduce clusters.

Near threshold voltage computing enables transistor voltage scaling to continue with Moore's Law projection and dramatically improves power and energy efficiency. However, reducing the supply voltage to near-threshold level significantly increases the susceptibility of on-chip caches to process variations, leading to the high error rate. Most existing fault-tolerant schemes significantly sacrifice cache capacity and performance. In this paper, we propose a novel fault-tolerant cache architecture at near-threshold computing, which is suitable for high error rate memories. We first propose a variation-aware skewed-associative cache, and then redirect the faulty blocks to the error-free blocks based on it to explore the fault-tolerance cache design. Unlike previous cache reconfiguration schemes for the fault tolerance, our cache design does not need to sacrifice or disable any fault-free blocks to form a completely functional set. We use all error-free blocks and have the least cache capacity waste. More importantly, since the aging impact could also cause cell failures, our skewed cache takes the aggregated process variation and aging impact into the consideration. Last but not least, our skewed cache design avoids the complex remapping from faulty blocks to the error-free blocks and minimizes the hardware overheads. Our evaluation results show that our variation-aware fault-tolerant cache design exhibits strong capability to tolerate the high error rate, and more excitingly, its effectiveness on reducing the cache miss rate and improving the performance is even more obvious as the supply voltage scales down to the near-threshold region.

In traditional radio-based localization methods, the target object has to carry a transmitter (e.g., active RFID), a receiver (e.g., 802.11 × detector), or a transceiver (e.g., sensor node). However, in some applications, such as safe guard systems, it is not possible to meet this precondition. In this paper, we propose a model of signal dynamics to allow the tracking of a transceiver-free object. Based on radio signal strength indicator (RSSI), which is readily available in wireless communication, three centralized tracking algorithms, and one distributed tracking algorithm are proposed to eliminate noise behaviors and improve accuracy. The midpoint and intersection algorithms can be applied to track a single object without calibration, while the best-cover algorithm has higher tracking accuracy but requires calibration. The probabilistic cover algorithm is based on distributed dynamic clustering. It can dramatically improve the localization accuracy when multiple objects are present. Our experimental test-bed is a grid sensor array based on MICA2 sensor nodes. The experimental results show that the localization accuracy for single object can reach about 0.8 m and for multiple objects is about 1 m.

Minimum disc cover problem which is NP-hard is kernel of node scheduling protocol in wireless sensor networks. Size of disc cover set obtained by approximate algorithm determines performance of node scheduling protocol. But the approximation ratios of present approximate algorithms aren't good. This paper proposes a local Voronoi diagrams-based approximate algorithm which can obtain a minimal disc cover set. Theoretical analyses show that the approximation ratio of this algorithm is less than 3. Experiments show that the size of disc cover set obtained by this algorithm is less than 43% of present algorithms and the average coverage degree is around 2.11 which are 1.7 times of optimal.

Wireless sensor networks have posed a number of challenging problems such as localization, deployment and tracking, etc. One of the interesting problems is the calculation of the coverage path for sensor networks. In this paper, we design a localized algorithm to solve the worst coverage problem first introduced by Meguerdichian et al. All nodes cooperate to construct the worst coverage path with their one-hop neighbors’ information. Also, the correctness of the algorithm is proved under the diminishing model formally.