Maximum Inner Product Search (MIPS) is a popular task to find the vector with the highest inner product for a given query. ScaNN is a score-aware quantization approach for MIPS that effectively transforms vectors with higher inner products into short sequences of codewords within codebooks. When quantizing vectors, it iteratively updates codebooks by assigning vectors to codewords and computing inverse matrices obtained from the assigned vectors. ScaNN, however, incurs a high computation cost when quantizing large-scale data. This is because (1) it computes quantization losses for all pairs of vectors and codewords, and (2) the size of the inverse matrices is quadratic in the number of dimensions. Our proposal, F-ScaNN, increases the efficiency of ScaNN through two techniques: (1) it computes the upper and lower bounds of the losses to assign vectors, and (2) it employs the conjugate gradient method to avoid computing the inverse matrix. Theoretically, we can obtain the same quantization results as ScaNN. Furthermore, we can improve search accuracy by using scaled codewords. Experiments show that our approach is significantly faster than previous approaches.

Attention mechanisms have played a crucial role in the success of Transformer models, as seen in platforms like ChatGPT. However, since they compute attentions from relationships between only one or two object types, they fail to effectively capture multi-object relationships in real-world scenarios, resulting in low prediction accuracy. In fact, they cannot calculate attention weights among diverse object types, such as the `comments,' `replies,' and `subjects' that naturally constitute conversations on platforms like Reddit or X, representing relationships simultaneously observed in real-world contexts. To overcome this limitation, we introduce the Tensorized Attention Model (TAM), which uses the Tucker decomposition to calculate attention weights across various object types and seamlessly integrates them into the Transformer models. Evaluations show that TAM significantly outperforms existing encoder methods, and its integration into the LoRA adapter for Llama2 enhances fine-tuning accuracy.

Makoto Nakatsuji, Shuhei Tateishi, Yasuhiro Fujiwara, Ayaka Matsumoto, Narichika Nomoto, Yoshihide Sato. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.

Facilitating self-disclosure without causing discomfort remains a difficult task—especially for AI systems. In real-world applications such as career counseling, wellbeing support, and onboarding interviews, eliciting personal information like concerns, goals, and personality traits is essential. However, asking such questions directly often leads to discomfort and disengagement. We address this issue with RaPSIL (Rapport-aware Preference-guided Self-disclosure Interview Learner), a two-stage LLM-based system that fosters natural, engaging conversations to promote self-disclosure. In the first stage, RaPSIL selectively imitates interviewer utterances that have been evaluated by LLMs for both strategic effectiveness and social sensitivity. It leverages LLMs as multi-perspective judges in this selection process. In the second stage, it conducts self-play simulations, using the Reflexion framework to analyze failures and expand a database with both successful and problematic utterances. This dual learning process allows RaPSIL to go beyond simple imitation, improving its ability to handle sensitive topics naturally by learning from both successful and failed utterances. In a comprehensive evaluation with real users, RaPSIL outperformed baselines in enjoyability, warmth, and willingness to re-engage, while also capturing self-descriptions more accurately. Notably, its impression scores remained stable even during prolonged interactions, demonstrating its ability to balance rapport building with effective information elicitation. These results show that RaPSIL enables socially aware AI interviewers capable of eliciting sensitive personal information while maintaining user trust and comfort—an essential capability for real-world dialogue systems.

Multimodal learning is generally expected to make more accurate predictions than text-only analysis. Here, although various methods for fusing multimodal inputs have been proposed for sentiment analysis tasks, we found that they may be inhibiting their fusion methods, which are based on attention-based language models, from learning non-verbal modalities, because non-verbal ones are isolated from the linguistic semantics and contexts and do not include them, meaning that they are unsuitable for applying attention to text modalities during the fusion phase. To address this issue, we propose Word-aware Modality Stimulation Fusion (WA-MSF) for facilitating integration of non-verbal modalities with the text modality. The Modality Stimulation Unit layer (MSU-layer) is the core concept of WA-MSF; it integrates language contexts and semantics into non-verbal modalities, thereby instilling linguistic essence into these modalities. Moreover, WA-MSF uses aMLP in the fusion phase in order to utilize spatial and temporal representations of non-verbal modalities more effectively than transformer fusion. In our experiments, WA-MSF set a new state-of-the-art level of performance on sentiment prediction tasks.

K-Multiple-Means is an extension of K-means for the clustering of multiple means used in many applications, such as image segmentation, load balancing, and blind-source separation. Since K-means uses only one mean to represent each cluster, it fails to capture non-spherical cluster structures of data points. However, since K-Multiple-Means represents the cluster by computing multiple means and grouping them into specified c clusters, it can effectively capture the non-spherical clusters of the data points. To obtain the clusters, K-Multiple-Means updates a similarity matrix of a bipartite graph between the data points and the multiple means by iteratively computing the leading c singular vectors of the matrix. K-Multiple-Means, however, incurs a high computation cost for large-scale data due to the iterative SVD computations. Our proposal, F-KMM, increases the efficiency of K-Multiple-Means by computing the singular vectors from a smaller similarity matrix between the multiple means obtained from the similarity matrix of the bipartite graph. To compute the similarity matrix of the bipartite graph efficiently, we skip unnecessary distance computations and estimate lower bounding distances between the data points and the multiple means. Theoretically, the proposed approach guarantees the same clustering results as K-Multiple-Means since it can exactly compute the singular vectors from the similarity matrix between the multiple means. Experiments show that our approach is several orders of magnitude faster than previous clustering approaches that use multiple means.

This paper tackles the goal of conclusion-supplement answer generation for non-factoid questions, which is a critical issue in the field of Natural Language Processing (NLP) and Artificial Intelligence (AI), as users often require supplementary information before accepting a conclusion. The current encoder-decoder framework, however, has difficulty generating such answers, since it may become confused when it tries to learn several different long answers to the same non-factoid question. Our solution, called an ensemble network, goes beyond single short sentences and fuses logically connected conclusion statements and supplementary statements. It extracts the context from the conclusion decoder's output sequence and uses it to create supplementary decoder states on the basis of an attention mechanism. It also assesses the closeness of the question encoder's output sequence and the separate outputs of the conclusion and supplement decoders as well as their combination. As a result, it generates answers that match the questions and have natural-sounding supplementary sequences in line with the context expressed by the conclusion sequence. Evaluations conducted on datasets including “Love Advice” and “Arts & Humanities” categories indicate that our model outputs much more accurate results than the tested baseline models do.

Machine reading comprehension methods that gen- erate answers by referring to multiple passages for a question have gained much attention in AI and NLP communities. The current methods, however, do not investigate the relationships among multi- ple passages in the answer generation process, even though topics correlated among the passages may be answer candidates. Our method, called neural answer Generation through Unified Memories over Multiple Passages (GUM-MP), solves this problem as follows. First, it determines which tokens in the passages are matched to the question. In particular, it investigates matches between tokens in positive passages, which are assigned to the question, and those in negative passages, which are not related to the question. Next, it determines which tokens in the passage are matched to other passages assigned to the same question and at the same time it investi- gates the topics in which they are matched. Finally, it encodes the token sequences with the above two matching results into unified memories in the pas- sage encoders and learns the answer sequence by using an encoder-decoder with a multiple-pointer- generator mechanism. As a result, GUM-MP can generate answers by pointing to important tokens present across passages. Evaluations indicate that GUM-MP generates much more accurate results than the current models do.

Analyzing “what topics” a user discusses with others is important in social network analysis. Since social relationships can be represented as multiobject relationships (e.g., those composed of a user, another user, and the topic of communication), they can be naturally represented as a tensor. By factorizing the tensor, we can perform communication prediction that predicts links among users and the topics discussed among them. The prediction accuracy, however, is often inadequate for applications because: 1) users usually discuss a variety of topics, and thus the prediction results tend to be biased toward popular domains and 2) topics that are rarely discussed among users trigger the sparsity problem in tensor factorization. Our solution, cross-domain tensor factorization (CrTF), first determines the topic domain by analyzing communication logs among users using the DBpedia knowledge base and creates a tensor composed of users, other users, and the topics of communication for each domain; it avoids strong bias toward particular domains. It then simultaneously factorizes tensors across domains while integrating semantics from DBpedia into factorizations; this solves the sparsity problem. Experiments using Twitter data sets show that CrTF achieves higher accuracy than the state-ofthe-art tensor-based methods and extracts key topics and social influencers for each domain.

The ability to predict the activities of users is an important one for recommender systems and analyses of social media. User activities can be represented in terms of relationships involving three or more things (e.g. when a user tags items on a webpage or tweets about a location he or she visited). Such relationships can be represented as a tensor, and tensor factorization is becoming an increasingly important means for predicting users' possible activities. However, the prediction accuracy of factorization is poor for ambiguous and/or sparsely observed objects. Our solution, Semantic Sensitive Tensor Factorization (SSTF), incorporates the semantics expressed by an object vocabulary or taxonomy into the tensor factorization. SSTF first links objects to classes in the vocabulary (taxonomy) and resolves the ambiguities of objects that may have several meanings. Next, it lifts sparsely observed objects to their classes to create augmented tensors. Then, it factorizes the original tensor and augmented tensors simultaneously. Since it shares semantic knowledge during the factorization, it can resolve the sparsity problem. Furthermore, as a result of the natural use of semantic information in tensor factorization, SSTF can combine heterogeneous and unbalanced datasets from different Linked Open Data sources. We implemented SSTF in the Bayesian probabilistic tensor factorization framework. Experiments on publicly available large-scale datasets using vocabularies from linked open data and a taxonomy from WordNet show that SSTF has up to 12% higher accuracy in comparison with state-of-the-art tensor factorization methods.

This paper focuses on task assignments to workers in mobile crowdsoucing systems. The current method does not work so well since it considers only workers who are ready to work at the time of optimization. Our method handles workers' day-long schedules, creates a `time-extended' worker-task graph that expresses the relationships between workers and tasks over a time period and finds the best set of worker-task-time triples. Our evaluation using real world visiting logs shows it increases the rate of assigned tasks by more than 8.2% compared with a state-of-the-art assignment method.

Affinity Propagation is a clustering algorithm used in many applications. It iteratively updates messages between data points until convergence. The message updating process enables Affinity Propagation to have higher clustering quality compared with other approaches. However, its computation cost is high; it is quadratic in the number of data points. This is because it updates the messages of all data point pairs. This paper proposes an efficient algorithm that guarantees the same clustering results as the original algorithm. Our approach, F-AP, is based on two ideas: (1) it computes upper and lower estimates to limit the messages to be updated in each iteration, and (2) it dynamically detects converged messages to efficiently skip unneeded updates. Experiments show that F-AP is much faster than previous approaches with no loss in clustering performance.

Predicting human activities is important for improving recommender systems or analyzing social relationships among users. Those human activities are usually repre- sented as multi-object relationships (e.g. user’s tagging activities for items or user’s tweeting activities at some locations). Since multi-object relationships are naturally represented as a tensor, tensor factorization is becom- ing more important for predicting users’ possible ac- tivities. However, its prediction accuracy is weak for ambiguous and/or sparsely observed objects. Our so- lution, Semantic data Representation for Tensor Fac- torization (SRTF), tackles these problems by incorpo- rating semantics into tensor factorization based on the following ideas: (1) It first links objects to vocabu- laries/taxonomies and resolves the ambiguity caused by objects that can be used for multiple purposes. (2) It next links objects to composite classes that merge classes in different kinds of vocabularies/taxonomies (e.g. classes in vocabularies for movie genres and those for directors) to avoid low prediction accuracy caused by rough-grained semantics. (3) It then lifts sparsely observed objects into their classes to solve the sparsity problem for rarely observed objects. To the best of our knowledge, this is the first study that leverages seman- tics to inject expert knowledge into tensor factorization. Experiments show that SRTF achieves up to 10% higher accuracy than state-of-the-art methods.

Subjective assessments (SAs), such as “elegant” and “gorgeous,” are assigned to items by users, and they are common in the reviews and tags found on many online sites. Analyzing the linked information provided by an SA assigned by a user to an item can improve the recommendation accuracy. This is because this information contains the reason why the user assigned a high or low rating value to the item. However, previous studies have failed to use SAs in an effective manner to improve the recommendation accuracy because few users rate the same items with the same SAs, which leads to the sparsity problem during collaborative filtering. To overcome this problem, we propose a novel method, called Linked Taxonomies , which links a taxonomy of items to a taxonomy of SAs to capture the userʼs interests in detail. First, our method groups the SAs assigned by users to an item into subjective classes (SCs), which are defined using a taxonomy of SAs such as those in WordNet, and they reflect the SAs/SCs assigned to an item based on their classes. Thus, our method can measure the similarity of users based on the SAs/SCs assigned to items and their classes (item classes are defined using a taxonomy of items), which overcomes the sparsity problem. Furthermore, SAs that are ineffective for accurate recommendations are excluded automatically from the taxonomy of SAs using this method. This is highly beneficial for the designers of taxonomies of SAs because it helps to ensure the production of accurate recommendations. We conducted investigations using a movie ratings/tags dataset with a taxonomy of SAs extracted from WordNet and a restaurant ratings/reviews dataset with an expert-created taxonomy of SAs, which demonstrated that our method generated more accurate recommendations than previous methods.

To obtain high PageRank score nodes, the original approach iteratively computes the Page-Rank score of each node until convergence by using the whole graph. If the graph is large, this approach is infeasible due to its high computational cost. The goal of this study is to find top-k Page\-Rank score nodes efficiently for a given graph without sacrificing accuracy. Our solution, F-Rank, is based on two ideas: (1) It iteratively estimates lower/upper bounds of Page\-Rank scores, and (2) It constructs subgraphs in each iteration by pruning unnecessary nodes and edges to identify top-k nodes. Our theoretical analysis shows that F-Rank guarantees result exactness. Experiments show that F-Rank finds top-k nodes much faster than the original approach.

Graphs are a fundamental data structure and have been employed to model objects as well as their relationships. The similarity of objects on the web (e.g., webpages, photos, music, micro-blogs, and social networking service users) is the key to identifying relevant objects in many recent applications. SimRank, proposed by Jeh and Widom, provides a good similarity score and has been successfully used in many applications such as web spam detection, collaborative tagging analysis, link prediction, and so on. SimRank computes similarities iteratively, and it needs O(N4T) time and O(N2) space for similarity computation where N and T are the number of nodes and iterations, respectively. Unfortunately, this iterative approach is computationally expensive. The goal of this work is to process top-k search and range search efficiently for a given node. Our solution, SimMat, is based on two ideas: (1) It computes the approximate similarity of a selected node pair efficiently in non-iterative style based on the Sylvester equation, and (2) It prunes unnecessary approximate similarity computations when searching for the high similarity nodes by exploiting estimations based on the Cauchy-Schwarz inequality. These two ideas reduce the time and space complexities of the proposed approach to O(Nn) where n is the target rank of the low-rank approximation (n ≪ N in practice). Our experiments show that our approach is much faster, by several orders of magnitude, than previous approaches in finding the high similarity nodes.

Personalized PageRank (PPR) has been successfully applied to various applications. In real applications, it is important to set PPR parameters in an ad-hoc manner when finding similar nodes because of dynamically changing nature of graphs. Through interactive actions, interactive similarity search supports users to enhance the efficacy of applications. Unfortunately, if the graph is large, interactive similarity search is infeasible due to its high computation cost. Previous PPR approaches cannot effectively handle interactive similarity search since they need precomputation or approximate computation of similarities. The goal of this paper is to efficiently find the top-k nodes with exact node ranking so as to effectively support interactive similarity search based on PPR. Our solution is Castanet. The key Castanet operations are (1) estimate upper/lower bounding similarities iteratively, and (2) prune unnecessary nodes dynamically to obtain top-k nodes in each iteration. Experiments show that our approach is much faster than existing approaches.

Personalize PageRank (PPR) is an effective relevance (proximity) measure in graph mining. The goal of this paper is to efficiently compute single node relevance and top-k/highly relevant nodes without iteratively computing the relevances of all nodes. Based on a "random surfer model", PPR iteratively computes the relevances of all nodes in a graph until convergence for a given user preference distribution. The problem with this iterative approach is that it cannot compute the relevance of just one or a few nodes. The heart of our solution is to compute single node relevance accurately in non-iterative manner based on sparse matrix representation, and to compute top-k/highly relevant nodes exactly by pruning unnecessary relevance computations based on upper/lower relevance estimations. Our experiments show that our approach is up to seven orders of magnitude faster than the existing alternatives.

Graphs are fundamental data structures and have been employed for centuries to model real-world systems and phenomena. Random walk with restart (RWR) provides a good proximity score between two nodes in a graph, and it has been successfully used in many applications such as automatic image captioning, recommender systems, and link prediction. The goal of this work is to find nodes that have top-k highest proximities for a given node. Previous approaches to this problem find nodes efficiently at the expense of exactness. The main motivation of this paper is to answer, in the affirmative, the question, 'Is it possible to improve the search time without sacrificing the exactness?'. Our solution, K-dash , is based on two ideas: (1) It computes the proximity of a selected node efficiently by sparse matrices, and (2) It skips unnecessary proximity computations when searching for the top-k nodes. Theoretical analyses show that K-dash guarantees result exactness. We perform comprehensive experiments to verify the efficiency of K-dash. The results show that K-dash can find top-k nodes significantly faster than the previous approaches while it guarantees exactness.

Most recommender algorithms produce types similar to those the active user has accessed before. This is because they measure user similarity only from the co-rating behaviors against items and compute recommendations by analyzing the items possessed by the users most similar to the active user. In this paper, we define item novelty as the smallest distance from the class the user accessed before to the class that includes target items over the taxonomy. Then, we try to accurately recommend highly novel items to the user. First, our method measures user similarity by employing items rated by users and a taxonomy of items. It can accurately identify many items that may suit the user. Second, it creates a graph whose nodes are users; weighted edges are set between users according to their similarity. It analyzes the user graph and extracts users that are related on the graph though the similarity between the active user and each of those users is not high. The users so extracted are likely to have highly novel items for the active user. An evaluation conducted on several datasets finds that our method accurately identifies items with higher novelty than previous methods.

Content providers want to make recommendations across multiple interrelated domains such as music and movies. However, existing collaborative filtering methods fail to accurately identify items that may be interesting to the user but that lie in domains that the user has not accessed before. This is mainly because of the paucity of user transactions across multiple item domains. Our method is based on the observation that users who share similar items or who share social connections, can provide recommendation chains (sequences of transitively associated edges) to items in other domains. It first builds domain-specific-usergraphs (DSUGs) whose nodes, users, are linked by weighted edges that reflect user similarity. It then connects the DSUGs via the users who rated items in several domains or via the users who share social connections, to create a cross-domain-user graph (CDUG). It performs Random Walk with Restarts on the CDUG to extract user nodes that are related to the starting user node on the CDUG even though they are not present in the DSUG of the starting user node. It then adds items possessed by those users to the recommendations of the starting node user. Furthermore, to extract many more user nodes, we employ a taxonomy-based similarity measure that states that users are similar if they share the same items and/or same classes. Thus we can set many suitable routes from the starting user node to other user nodes in the CDUG. An evaluation using rating datasets in two interrelated domains and social connection histories of users as extracted from a blog portal, indicates that our method identifies potentially interesting items in other domains with higher accuracy than is possible with existing CF methods.

These days, many companies are executing their business aims based on decentralized cooperation of software components which work on various systems over a network. However, messages and processes between systems are designed individually in each operations division. Therefore, the system development for adjusting interfaces is expensive, so the companies cannot introduce their services in a dynamic business environment. To resolve such problems, we propose interface modeling technique and message mapping technique which model the relationship between the message formats and semantics on the formats by using Web Ontology Language (OWL) and execute the mapping between the message formats by using semantics. We developed the user interactive message mapping tool and evaluated our proposed methods based on the interface specifications of real network management systems.