Large Language Models (LLMs) are increasingly employed in applications that require processing information from heterogeneous formats, including texts, tables, infoboxes, and knowledge graphs. However, systematic biases toward particular formats may undermine LLMs' ability to integrate heterogeneous data impartially, potentially resulting in reasoning errors and increased risks in downstream tasks. Yet it remains unclear whether such biases are systematic, which data-level factors drive them, and what internal mechanisms underlie their emergence. In this paper, we present the first comprehensive study of format bias in LLMs through a three-stage empirical analysis. The first stage explores the presence and direction of bias across a diverse range of LLMs. The second stage examines how key data-level factors influence these biases. The third stage analyzes how format bias emerges within LLMs' attention patterns and evaluates a lightweight intervention to test its effectiveness. Our results show that format bias is consistent across model families, driven by information richness, structure quality, and representation type, and is closely associated with attention imbalance within the LLMs. Based on these investigations, we identify three future research directions to reduce format bias: enhancing data pre-processing through format repair and normalization, introducing inference-time interventions such as attention re-weighting, and developing format-balanced training corpora. These directions will support the design of more robust and fair heterogeneous data processing systems.

Large Language Models (LLMs) often suffer from hallucinations and outdated or incomplete knowledge. Retrieval-Augmented Generation (RAG) is proposed to address these issues by integrating external knowledge like that in knowledge graphs (KGs) into LLMs. However, leveraging private KGs in RAG systems poses significant privacy risks due to the black-box nature of LLMs and potential insecure data transmission. In this paper, we investigate the privacy-protected RAG scenario for the first time, where entities in KGs are anonymous for LLMs, thus preventing them from accessing entity semantics. Due to the loss of semantics of entities, previous RAG systems cannot retrieve question-relevant knowledge from KGs by matching questions with the meaningless identifiers of anonymous entities. To realize an effective RAG system in this scenario, two key challenges must be addressed: (1) How can anonymous entities be converted into retrievable information? (2) How to retrieve question-relevant anonymous entities? To address these challenges, we propose a novel Abstraction Reasoning on Graph (ARoG) framework including relation-centric abstraction and structure-oriented abstraction strategies. For challenge (1), the first strategy abstracts entities into high-level concepts by dynamically capturing the semantics of their adjacent relations. Hence, it supplements meaningful semantics which can further support the retrieval process. For challenge (2), the second strategy transforms unstructured natural language questions into structured abstract concept paths. These paths can be more effectively aligned with the abstracted concepts in KGs, thereby improving retrieval performance. In addition to guiding LLMs to effectively retrieve knowledge from KGs, these abstraction strategies also strictly protect privacy from being exposed to LLMs. Experiments on three datasets demonstrate that ARoG achieves strong performance and privacy-robustness, establishing a new practical direction for privacy-protected RAG systems.

Yongqi Li, Shen Zhou, Xiaohu Li, Xin Miao, Jintao Wen, Mayi Xu, Jianhao Chen, Birong Pan, Hankun Kang, Yuanyuan Zhu, Ming Zhong, Tieyun Qian. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.

In temporal graphs, time and topology are considered to be intertwined. As an evidence, it is observed that the vertices in more cohesive subgraphs have more frequent and more numerous interactions between each other in the history. Motivated by that, we study a novel frequency-aware k-core query problem. Different from previous studies that focus on finding k-cores in the projected subgraphs of given time intervals, we look for the subgraphs of k-core in which neighbor vertices have at least a certain number of high-frequency interactions. To address the problem, we propose 1) a minimum slope algorithm for computing the frequency in linear time, 2) a space-efficient index that stores the distinct “core frequency” of vertices for addressing arbitrary queries, 3) a propagation algorithm that collects core frequencies by message passing for index construction, and 4) efficient algorithms for retrieving a specific or all skyline results from the index respectively. The experimental results show that, our algorithms achieve several orders of magnitude improvement on efficiency compared to corresponding baselines, and meanwhile, the size of index is even smaller than that of graph unless the graph has very few timestamps on each edge. More importantly, by both statistics and case study, it is verified that the frequency-aware k-core query indeed find more cohesive subgraphs in the static k-core.

Truss decomposition is to find the hierarchy of all the k-trusses in a graph for$k\geq 2$. Existing GPU-based algorithms first compute edge support by parallelly counting the number of triangles each edge is contained in, and then iteratively peel off edges with the smallest support and update support of the affected edges in parallel. However, these algorithms perform truss decomposition on undirected graphs, which causes large storage space and numerous triangle existence checks during support update. Moreover, they are developed based on CUDA, which cannot naturally adapt to emerging hardware accelerators and support the end-to-end downstream graph machine learning (ML) tasks. In this paper, we propose a truss decomposition framework based on tensors (TDT), which can leverage the parallelism of heterogeneous hardware backends to speed up the computation and seamlessly integrate with downstream graph ML tasks. We first convert the original input graph into a directed graph and represent it by compacted tensors. Then we perform truss decomposition on the tensorized directed graph by efficient tensor operators. Such a directed-graph storage model not only saves the storage space but also naturally supports efficient support computation/update during the truss decomposition. To further accelerate truss decomposition, we also partition vertex neighbors into blocks to balance the computation workload and optimize key steps such as support computation/update in our framework. Extensive experimental studies show that our Python-based TDT algorithm not only achieves$2.3\times-8.5\times$speedup in most cases compared with the state-of-the-art CUDA-based algorithms, but also can efficiently deal with large graphs with hundreds of millions of nodes and billions of edges while the baseline fails due to large storage cost. Our source code is publicly available at https://github.com/LiGuojing194/TDTdecomposition.

Graph Neural Networks (GNNs) have been demonstrated to be vulnerable to backdoor attacks, which hinder their deployment in security-sensitive applications such as intrusion detection and fraud detection. Existing backdoor detection approaches often rely on access to poisoned samples or make assumptions about attack strategies, thereby limiting their effectiveness in real-world scenarios. We propose a model-level approach, Neighbor Pattern-Based Backdoor Detection (NPBD), to eliminate these limitations. Our approach introduces the Contextual Stochastic Block Model for Neighbor Patterns (CSBM-NP) to generate synthetic graphs with diverse and controlled neighbor patterns, including those not typically found in real-world datasets. These synthetic graphs are then optimized to enhance the discriminative features that enable the classifier to distinguish backdoored models from benign ones. We validate the effectiveness and generalizability of our detection approach through comprehensive experiments, achieving average detection AUC values of 0.99, 0.97, 0.91, and 0.92 on the Cora, PubMed, Flickr, and OGB-arxiv datasets, respectively, surpassing existing detection approaches.

With the development of AI and the growing demand for computational power, hardware is becoming increasingly specialized and heterogeneous. The emergence of diverse specialized hardware architectures, each with distinct characteristics and programming abstractions, poses significant portability and sustainability challenges for existing data processing systems. Tensor Computation Runtimes (TCRs) abstract away the low-level hardware complexities by providing users with a hardware-independent tensor-based interface, enabling data scientists to effectively leverage the powerful capabilities of new hardware accelerators (collectively referred to as XPU). Built on TCRs, the existing relational query engine TQP demonstrates portability across a wide range of target hardware and sustainability along with the ongoing evolution of TCRs and hardware. However, it neglects the big gap between irregular SQL workloads and uniform tensor operations when mapping SQL operators to tensor programs, which causes significant storage and computation overhead. In this paper, for the first time, we analyze the underlying gap between SQL and tensors, and provide guidelines to bridge it. Following these guidelines, we build a new Tensor-based Query Engine Enhanced (TQEx) by bridging the gap from multiple aspects: develop efficient storage and computation strategies for variable-length data, and design efficient SQL operators such as join and aggregate based on tensors. We also extend TQEx to multi-XPUs for large-scale data processing. Extensive experimental studies show that our query engine, TQEx, achieves a 9.6× speedup (with a peak of 41.9×) over TQP on TPC-H, and it is also 27.9× faster than leading GPU databases such as HeavyDB. On TPC-H at scale factor 100, TQEx outperforms DuckDB by 12.2× and HeavyDB by 22.7× on supported queries.

Graph is ubiquitous in various real-world applications, and many graph processing systems have been developed. Recently, hardware accelerators have been exploited to speed up graph systems. However, such hardware-specific systems are hard to migrate across different hardware backends. In this paper, we propose the first tensor-based graph processing framework, Tgraph, which can be smoothly deployed and run on any powerful hardware accelerators (uniformly called XPU) that support Tensor Computation Runtimes (TCRs). TCRs, which are deep learning frameworks along with their runtimes and compilers, provide tensor-based interfaces to users to easily utilize specialized hardware accelerators without delving into the complex low-level programming details. However, building an efficient tensor-based graph processing framework is non-trivial. Thus, we make the following efforts: (1) propose a tensor-centric computation model for users to implement graph algorithms with easy-to-use programming interfaces; (2) provide a set of graph operators implemented by tensor to shield the computation model from the detailed tensor operators so that Tgraph can be easily migrated and deployed across different TCRs; (3) design a tensor-based graph compression and computation strategy and an out-of-XPU-memory computation strategy to handle large graphs. We conduct extensive experiments on multiple graph algorithms (BFS, WCC, SSSP, etc.), which validate that Tgraph not only outperforms seven state-of-the-art graph systems, but also can be smoothly deployed and run on multiple DL frameworks (PyTorch and TensorFlow) and hardware backends (Nvidia GPU, AMD GPU, and Apple MPS).

The recently proposed historical k -core query introduces a new paradigm of structure analysis for temporal graphs. However, the query processing based on the existing PHC-index, which preserves the distinct "core time" of each vertex, needs to traverse all vertices for each query, even though the results usually contain only a small subset of vertices. Inspired by the traditional k -shell that ensures the optimal k -core query processing, we propose a novel concept called "core time shell", which reveals the hierarchical structure of vertices with respect to their core time. Based on the core time shell, we design a time-space balanced Merged Core Time Shell index (MCTS-index). It is theoretically guaranteed that, the MCTS-index provides the approximately optimal query performance, and has the approximately same space complexity as the PHC-index. Moreover, we leverage the MCTS-index to efficiently address the brand-new "when" historical k -core queries orthogonal to the current "what" historical k -core queries. Our experimental results on ten real-world temporal graphs demonstrate both the superior efficiency of processing "what" queries and the effectiveness of processing versatile "when" queries for the MCTS-index.

Identifying protein complexes from protein-protein interaction (PPI) networks is essential for understanding cellular organization and biological processes. Most of the existing works treat PPI networks as static and focus on detecting densely connected regions. Several recent works have explored the dynamics of PPIs in the network, but may identify complexes with false-positive edges of low confidence. In this paper, we propose a novel Dynamic COre-ATtachment based protein complex detection algorithm (DCOAT). First, we derive co-expressed gene biclusters from the gene expression data by a memetic algorithm to enable the construction of dynamic subnetworks from a static PPI network. Next, we evaluate the confidence of edges within each dynamic subnetwork by integrating both topological features and biological information to filter false-positive edges. Then, we detect complexes from each weighted subnetwork based on the core-attachment structure. Finally, we build an overlapping graph and merge redundant complexes using maximum weight matching. The experimental results validate that DCOAT achieves state-of-the-art performance compared to the nine baseline methods based on static and dynamic networks across multiple evaluation measures, especially in terms of F1and precision. Moreover, the detected stable and temporal complexes are consistent with real biological scenarios and have biological significance. Our code and datasets are publicly available at https://github.com/LiGuojing194/DCOAT.

The recent prosperity of temporal graph research redefines many traditional concepts on static graphs, such as triangle, motif,$k$-core, etc. Inspired by that, we propose a novel$(k, \delta)$-truss on temporal graphs, which requires its triangles to exist in short enough time windows ever. The$(k,\delta)$-truss satisfies both static and temporal cohesion, while the original$k$-truss is its special case when$\delta=\infty$. In order to address the$(k, \delta)$-truss query, we propose both index-free and index-based approaches. By leveraging the dual containment relation on$(k, \delta)$-trusses, our indexes can compress all$(k, \delta)$-trusses losslessly into map or tree structures with dramatically less space, so that a specific$(k,\ \delta)$-truss can be retrieved from indexes in the optimal time. To enable our index to scale to large temporal graphs, we develop two index construction algorithms that can reduce redundant computation significantly, based on truss decomposition and truss maintenance respectively. The experimental results demonstrate that index-based approaches process queries in interactive time and outperform the index-free approach by 2~4 orders of magnitude, while indexes achieve compression ratios up to 10-4.

For a temporal graph like transaction network, finding a densely connected subgraph that contains a vertex like a suspicious account during a period is valuable. Thus, we study the Temporal k -Core Component Search (TCCS) problem, which aims to find a connected component of temporal k -core for any given vertex and time interval. Towards this goal, we propose a novel Evolution Forest Index (EF-Index) that can address TCCS in optimal time. Essentially, EF-Index leverages the evolutionary order on temporal k -cores to both compress the connectivity between vertices in temporal k -cores of all time intervals into a minimum set of compactest Minimum Temporal Spanning Forests (MTSFs) and retrieve MTSF for a given time interval rapidly. Here, a crucial innovation is that, we extend the temporal k -core evolution theory by introducing a pair of time-topology isomorphic relations, on top of which the evolutionary order in topology domain can be simply computed by a "kernel function" in time domain. Moreover, we design an efficient mechanism to update EF-Index incrementally for dynamic edge streams. The experimental results on a variety of real-world temporal graphs demonstrate that, EF-Index outperforms the state-of-the-art approach by 1--3 orders of magnitude on processing TCCS, and its space overhead is reduced by 4--5 orders of magnitude compared with preserving connectivity uncompressedly.

Querying cohesive subgraphs on temporal graphs (e.g., social network, finance network, etc.) with various conditions has attracted intensive research interests recently. In this paper, we study a novel Temporal$(k,\mathcal {X})$-Core Query (TXCQ) that extends a fundamental Temporal$k$-Core Query (TCQ) proposed in our conference paper by optimizing or constraining an arbitrary metric$\mathcal {X}$of$k$-core, such as size, engagement, interaction frequency, time span, burstiness, periodicity, etc. Our objective is to address specific TXCQ instances with conditions on different$\mathcal {X}$in a unified algorithm framework that guarantees scalability. For that, this journal paper proposes a taxonomy of measurement$\mathcal {X}(\cdot )$and achieve our objective using a two-phase framework while$\mathcal {X}(\cdot )$is time-insensitive or time-monotonic. Specifically, Phase 1 still leverages the query processing algorithm of TCQ to induce all distinct$k$-cores during a given time range, and meanwhile locates the “time zones” in which the cores emerge. Then, Phase 2 conducts fast local search and$\mathcal {X}$evaluation in each time zone with respect to the time insensitivity or monotonicity of$\mathcal {X}(\cdot )$. By revealing two insightful concepts named tightest time interval and loosest time interval that bound time zones, the redundant core induction and unnecessary$\mathcal {X}$evaluation in a zone can be reduced dramatically. Our experimental results demonstrate that TXCQ can be addressed as efficiently as TCQ, which achieves the latest state-of-the-art performance, by using a general algorithm framework that leaves$\mathcal {X}(\cdot )$as a user-defined function.

Emotion recognition in conversation, which aims to predict the emotion for all utterances, has attracted considerable research attention in recent years. It is a challenging task since the recognition of the emotion in one utterance involves many complex factors, such as the conversational context, the speaker's background, and the subtle difference between emotion labels. In this paper, we propose a novel framework which mimics the thinking process when modeling these factors. Specifically, we first comprehend the conversational context with a history-oriented prompt to selectively gather information from predecessors of the target utterance. We then model the speaker's background with an experience-oriented prompt to retrieve the similar utterances from all conversations. We finally differentiate the subtle label semantics with a paraphrasing mechanism to elicit the intrinsic label related knowledge. We conducted extensive experiments on three benchmarks. The empirical results demonstrate the superiority of our proposed framework over the state-of-the-art baselines.

Querying cohesive subgraphs on temporal graphs with various time constraints has attracted intensive research interests recently. In this paper, we study a novel Temporal k -Core Query (TCQ) problem: given a time interval, find all distinct k -cores that exist within any subintervals from a temporal graph, which generalizes the previous historical k -core query. This problem is challenging because the number of subintervals increases quadratically to the span of time interval. For that, we propose a novel Temporal Core Decomposition (TCD) algorithm that decrementally induces temporal k -cores from the previously induced ones and thus reduces "intra-core" redundant computation significantly. Then, we introduce an intuitive concept named Tightest Time Interval (TTI) for temporal k -core, and design an optimization technique with theoretical guarantee that leverages TTI as a key to predict which subintervals will induce duplicated k -cores and prunes the subintervals completely in advance, thereby eliminating "inter-core" redundant computation. The complexity of optimized TCD (OTCD) algorithm no longer depends on the span of query time interval but only the scale of final results, which means OTCD algorithm is scalable. Moreover, we propose a compact in-memory data structure named Temporal Edge List (TEL) to implement OTCD algorithm efficiently in physical level with bounded memory requirement. TEL organizes temporal edges in a "timeline" and can be updated instantly when new edges arrive in dynamical temporal graphs. We compare OTCD algorithm with the incremental historical k -core query on several real-world temporal graphs, and observe that OTCD algorithm outperforms it by three orders of magnitude, even though OTCD algorithm needs none precomputed index.

The semantic gap between keyword queries and search intents behind them motivates intensive studies on keyword query interpretation, which aims to interpret a keyword query to structured queries (a.k.a. patterns) representing most possibly relevant search intents. However, there still lacks of study on an important issue: how to guarantee the patterns are "reliable", which means the structured queries can be evaluated as really existing results. In this paper, we regard the reliability as a new metric for ranking patterns, and present a keyword query interpretation approach to find both reliable and relevant pattern trees on an arbitrary summary graph of underlying data. Specifically, we firstly propose a reliability estimation model to measure how possibly a pattern tree can be evaluated as a nonempty result set by statistics under reasonable assumptions. Secondly, we develop constrained top-k search algorithms that guarantee to return the optimal pattern trees for a specific keyword query. Moreover, to improve the efficiency of online search, we also design elaborate indexes, search heuristics and pruning strategies. Lastly, we perform comprehensive experiments on two real-world datasets, DBpedia and Yago, with both QALD-9 queries and random queries. The observations indicate our approach improves the accuracy and overall quality of top-k results significantly.

The performance of relation extraction (RE) is hindered by the lack of sufficient labeled data. Semisupervised methods can offer to help hands with this problem by augmenting high-quality unlabeled samples into the training data. However, existing semisupervised RE methods either need a set of manually defined rules or rely on the classifier trained on the small labeled data, i.e., the former requires the heavy intervention of human knowledge, and the latter is bound to the number and the quality of the labeled data. In this article, we present a novel semisupervised RE method that involves small human efforts and is robust to the size of the initial set of labeled data. Specifically, we adopt only two simple rules to build the lexical and semantic graphs which connect the labeled samples with the unlabeled ones. In this way, the graphs are much easier to construct yet keep the ability to transfer knowledge from labeled samples to unlabeled ones. We then develop a graph interaction module to fully exploit the reference information in lexical and semantic graphs, which is used to jointly recognize the high-quality unlabeled samples with the classifier. We conduct extensive experimental results on two public datasets. The results demonstrate that our proposed method significantly outperforms the state-of-the-art baselines.

The Point-of-Interest (POI) transition behaviors could hold absolute sparsity and relative sparsity very differently for different cities. Hence, it is intuitive to transfer knowledge across cities to alleviate those data sparsity and imbalance problems for next POI recommendation. Recently, pre-training over a large-scale dataset has achieved great success in many relevant fields, like computer vision and natural language processing. By devising various self-supervised objectives, pre-training models can produce more robust representations for downstream tasks. However, it is not trivial to directly adopt such existing pre-training techniques for next POI recommendation, due to thelacking of common semantic objects (users or items) across different cities. Thus in this paper, we tackle such a new research problem ofpre-training across different citiesfor next POI recommendation. Specifically, to overcome the key challenge that different cities do not share any common object, we propose a novel pre-training model namedCATUS, by transferring thecategory-leveluniversal transition knowledge over different cities. Firstly, we build two self-supervised objectives inCATUS:next category predictionandnext POI prediction, to obtain the universal transition-knowledge across different cities and POIs. Then, we design acategory-transition oriented sampleron the data level and animplicit and explicit transfer strategyon the encoder level to enhance this transfer process. At the fine-tuning stage, we propose adistance oriented samplerto better align the POI representations into the local context of each city. Extensive experiments on two large datasets consisting of four cities demonstrate the superiority of our proposedCATUSover the state-of-the-art alternatives. The code and datasets are available at https://github.com/NLPWM-WHU/CATUS.

Community search aims to find cohesive subgraphs containing certain vertices, attracting increasing interest recently. However, existing cohesive models such as k-core mainly focus on the dense connections inside the community, and neglect the interactions with the vertices outside. In this paper, we study the (k,p) -core community search (KPCS) problem in dynamic graphs, i.e., find the maximal connected subgraph containing a query vertex where each vertex has at least k neighbors and at least p fraction of its neighbors in the subgraph. Such fraction and connectivity constraints bring non-trivial challenges to the online community search in dynamic graphs. Thus, we design a space-efficient$O(m)$where$m$is the edge number) index KPForest which can support time-optimal (k,p) -core community search. We also propose novel construction and maintenance algorithms to record and update the (k,p) value and the connectivity information for dynamic graphs correctly and efficiently. Extensive experimental studies on ten real-world datasets show that our index can support community search with two orders of magnitude speedup at a small cost of construction and maintenance compared with the baseline algorithms.

Attributed networks are ubiquitous in the real world, such as social networks. Therefore, many researchers take the node attributes into consideration in the network representation learning to improve the downstream task performance. In this article, we mainly focus on an untouched "oversmoothing" problem in the research of the attributed network representation learning. Although the Laplacian smoothing has been applied by the state-of-the-art works to learn a more robust node representation, these works cannot adapt to the topological characteristics of different networks, thereby causing the new oversmoothing problem and reducing the performance on some networks. In contrast, we adopt a smoothing parameter that is evaluated from the topological characteristics of a specified network, such as small worldness or node convergency and, thus, can smooth the nodes' attribute and structure information adaptively and derive both robust and distinguishable node features for different networks. Moreover, we develop an integrated autoencoder to learn the node representation by reconstructing the combination of the smoothed structure and attribute information. By observation of extensive experiments, our approach can preserve the intrinsical information of networks more effectively than the state-of-the-art works on a number of benchmark datasets with very different topological characteristics.

Protein complexes are important functional units for performing biological functions and revealing cellular organization principles, and its detection is a fundamental problem in computational biology. In this paper, we present a novel algorithm COMNA by using orthology relationship across different species to complement the complex detection of a single protein-protein interaction (PPI) network, which can identify protein complexes from multiple PPI networks simultaneously. First, we propose a novel measure, high-order edge closure coefficient, to assess the reliability of interactions and then identify core-attachment based complexes from each PPI network. Second, we cooperate with the orthology information from multiple PPI network alignment to mine more complementary complexes. Finally, we merge the highly overlapping complexes by constructing an overlapping graph. We compare COMNA with eight state-of-the-art protein complex identification algorithms on three datasets, and the experimental results show that COMNA can detect complexes from PPI networks with higher accuracy.

Protein-protein interaction (PPI) network alignment aims to find a node mapping between nodes across networks for different specifies such that the mapped nodes are topologically and biologically similar. Such alignment can help to reveal functionally similar subnetworks and predict previously undiscovered orthologs of different species. Although many aligners have been proposed, few can find global alignments with both high topological and biological quality. In this paper, we propose a new pairwise global PPI network aligner (GPPIAL) based on orthologs. We first construct a score matrix to evaluate the matching possibility of node pairs by combining multiple sources of information, including the biological (sequence and functional), topological (degree and neighborhood), and interaction information. Then we select orthologs with high similarity scores in the Inparanoid database as anchor pairs, and gradually build a global alignment. We compare GPPIAL with the stateof-the-art pairwise global network aligners on multiple PPI network pairs from the BioGRID dataset. The results show that GPPIAL significantly outperforms existing global aligners in terms of biological quality without losing the topological quality. Moreover, GPPIAL can also detect more orthologous proteins than existing global aligners, and thus can be applied to predicting the function of unannotated proteins. Our code and datasets are available at https://github.com/whuyrc/GPPIAL.

Authorship attribution (AA) aims to identify the authors of a set of documents. Traditional studies in this area often assume that there are a large set of labeled documents available for training. However, in the real life, it is hard or expensive to collect a large set of labeled data. For example, in the online review domain, most reviewers (authors) only write a few reviews, which are not enough to serve as the training data for accurate classification. In this paper, we present a novel two-view co-training framework to iteratively identify the authors of a few unlabeled data to augment the training set. The key idea is to first represent each document as several distinct views, and then a co-training technique is adopted to exploit the large amount of unlabeled documents. Starting from 10 training texts per author, we systematically evaluate the effectiveness of co-training for authorship attribution with limited labeled data. Two methods and three views are investigated: logistic regression (LR) and support vector machines (SVM) methods, and character, lexical, and syntactic views. The experimental results show that LR is particularly effective for improving co-training in AA, and the lexical view performs the best among three views when combined with a LR classifier. Furthermore, the co-training framework does not make much difference between one classifier from two views and two classifiers from one view. Instead, it is the learning approach and the view that plays a critical role.

This paper presents a novel Chinese word segmentation approach combining both dictionary-based and statistics-based techniques. First, we transform a linear sentence to a word lattice based on dictionary. Then we apply classification method based on support vector machine to conduct two main tasks: resolving segmentation ambiguities and recognizing out-of-vocabulary words. We determine the position in word of the current character by using some of its surrounding characters as features. Disambiguation and recognition result in pruning and appending edges in the word lattice. Lastly, we output the segmentation results by searching the shortest path in the word lattice. Our experimental results show that our approach can achieve an F-score of 92.8% in PKU closed test of the second SIGHAN bakeoff.

As the ubiquitous interplay of structured, semi-structured and unstructured data from different sources, neither DB-style structured query requiring knowledge of full schema and complex language, nor IR-style keyword search ignoring latent structures, can satisfy users. In this paper, we present a novel Semi-Structured Search Engine (3SE) that provides easy, flexible, precise and rapid access to heterogeneous data represented by a semi-structured graph model.

Current keyword proximity search approaches on general graph lack effective means to reduce the search space, and thus suffer from low efficiency when dealing with large search space. In this paper, we present a novel approach in order to address this problem. Our approach employs a best-effort frontier-reduce strategy that aims to find a set of subgraphs containing the best answers. So we need only to search over these small subgraphs to get the top-k answers, and thus the efficiency can be significantly improved. To fulfill our strategy, we define a d-distance subgraph with upper size bound, and extract such subgraphs from the graph to build a new index structure combining the mappings between keywords, vertexes and subgraphs, by which we can quickly look up the target subgraphs for specific queries. Then, we perform an efficient algorithm to find the top-k answers, which can overcome the subgraph overlap problem and support existing optimal prioritization techniques.