Graph neural networks (GNNs) have achieved breakthroughs in various real-world downstream tasks due to their powerful expressiveness. As the scale of real-world graphs has been continuously growing, a storage-based approach to GNN training has been studied, which leverages external storage (e.g., NVMe SSDs) to handle such web-scale graphs on a single machine. Although such storage-based GNN training methods have shown promising potential in large-scale GNN training, we observed that they suffer from a severe bottleneck in data preparation since they overlook a critical challenge: how to handle a large number of small storage I/Os. To address the challenge, in this paper, we propose a novel storage-based GNN training framework, named AGNES, that employs a method of block-wise storage I/O processing to fully utilize the I/O bandwidth of high-performance storage devices. Moreover, to further enhance the efficiency of each storage I/O, AGNES employs a simple yet effective strategy, hyperbatch-based processing based on the characteristics of real-world graphs. Comprehensive experiments on five real-world graphs reveal that AGNES consistently outperforms four state-of-the-art methods, up to 4.1× faster than the best competitor.

Conversational recommender systems (CRSs) aim to provide personalized item recommendations along with explanations based on the conversations with users. While advancements in language models (LMs) have facilitated CRSs, limitations remain when LMs lack sufficient knowledge about item features that are essential for accurate recommendations and appropriate explanations. To alleviate this issue, retrieval-augmented language models (RALMs) have been introduced; however, they introduce a new challenge: the inclusion of less-relevant knowledge in retrieved passages. To address this limitation, we propose a novel CRS framework, MOCHA, which enhances RALMs through a multi-stage item/feature selection with Chain-of-Thought (CoT) reasoning. Specifically, MOCHA systematically identifies relevant knowledge by first selecting the item to recommend and then selecting its features to explain; each selection is performed via CoT reasoning. Experimental results on two public CRS datasets demonstrate that MOCHA significantly improves the recommendation accuracy, and provides informative and factually-correct explanations for the recommended items.

With the increasing size of real-world networks, efficient analysis of large-scale graphs has become an important research area. To this end, we can consider Processing-in-Memory (PIM), which integrates processing units and main memory into a single chip, as a promising solution. Many studies have focused on enabling highly efficient processing of memory-intensive tasks by using PIM's high internal bandwidth. To the best of our knowledge, however, there have been no studies related to the scenarios where the entire graph does not fit in main memory and data movement across storage, memory, and cache should be considered. Motivated by this, we propose RealGraph PIM, a new PIM-based graph engine, that processes large-scale real-world graphs efficiently on top of the original RealGraph, a state-of-the-art CPU-based graph engine. RealGraph PIM employs (1) asynchronous I/O to reduce wasting time in an idle state and (2) column-wise partitioning to reduce CPU workloads, thereby issuing I/O requests more frequently. Experimental results on real-world datasets show that RealGraph PIM outperforms dramatically state-of-the-art graph engines including a naive version of RealGraphPIM.

Real-world networks have high-order relationships among objects and they evolve over time. To capture such dynamics, many works have been studied in a range of fields. Via an in-depth preliminary analysis, we observe two important characteristics of high-order dynamics in real-world networks: high-order relations tend to (O1) have a structural and temporal influence on other relations in a short term and (O2) periodically re-appear in a long term. In this paper, we propose LINCOLN, a method for Learning hIgh-order dyNamiCs Of reaL-world Networks, that employs (1) bi-interactional hyperedge encoding for short-term patterns, (2) periodic time injection and (3) intermediate node representation for long-term patterns. Via extensive experiments, we show that LINCOLN outperforms nine state-of-the-art methods in the dynamic hyperedge prediction task.

Personalized news recommendation aims to deliver news articles aligned with users' interests, serving as a key solution to alleviate the problem of information overload on online news platforms. While prior work has improved interest matching through refined representations of news and users, the following time-related challenges remain underexplored: (C1) leveraging the age of clicked news to infer users' interest persistence, and (C2) modeling the varying lifetime of news across topics and users. To jointly address these challenges, we propose a novel Lifetime-aware Interest Matching framework for nEws recommendation, named LIME, which incorporates three key strategies: (1) User-Topic lifetime-aware age representation to capture the relative age of news with respect to a user-topic pair, (2) Candidate-aware lifetime attention for generating temporally aligned user representation, and (3) Freshness-guided interest refinement for prioritizing valid candidate news at prediction time. Extensive experiments on two real-world datasets demonstrate that LIME consistently outperforms a wide range of state-of-the-art news recommendation methods, and its model agnostic strategies significantly improve recommendation accuracy.

In the literature, various graph embedding methods have been proposed. Although they have pioneered notable techniques in the field, we point out their four drawbacks as follows: (1) inability to consider global graph structure(2) undermining learning quality(3) impairing in/out-degree distributions in directed graphs, and (4) limited applicability. Inspired by these drawbacks, we first propose LINOW, a recursive LI nk-based similarity measure for graphs by utilizing NO des' Weights, which is applicable to both directed and undirected graphs. Then, we provide a matrix form that dramatically accelerates LINOW's computation without approximation. Furthermore, to enhance its scalability, we provide two variants, LINOW-sn and LINOW-bn, to compute similarity scores w.r.t. a single node and a batch of nodes, respectively. Finally, we propose SIGEM, a simple yet effective self-supervised and contrastive-free SI milarity based Graph EM bedding method that employs LINOW-bn to compute similarity scores of nodes in the graph, thereby ranking them. Then, it tries to preserve the original ranks of nodes in the graph within their corresponding vectors in the embedding space, by employing a single-layer neural network. The results of our extensive experiments with eight real-world datasets and thirteen state-of-the-art and conventional embedding methods demonstrate that (1) LINOW-sn and LINOW-bn successfully improve the scalability of naive LINOW(2) LINOW is beneficial to similarity based graph embedding, and (3) SIGEM consistently achieves the highest accuracy in both graph reconstruction and node classification tasks compared to other methods, while it significantly outperforms them in most cases of the link prediction task.

Beyond using multimodal features of items in addition to user-item interactions, researchers have additionally utilized Contrastive Learning (CL) in recent multimedia recommender systems to highly alleviate the data sparsity problem. CL-based methods generate at least two embeddings (i.e., views) for each instance and enrich the information of each instance from various perspectives via the views, thereby alleviating the data sparsity problem. Therefore, CL-based methods have focused on generating views that effectively represent the characteristics of each instance for their downstream tasks. Similarly, CL-based multimedia recommender systems have made efforts to effectively generate their user/item views by leveraging items' multimodal features. However, we point out the following two limitations that they have overlooked in generating their views: (1) they either have not attempted to identify the influence of each modality feature of an item on user-item interactions, or have identified it by randomly masking or dropping user-item interactions, and (2) they have not attempted to identify non-interactions likely to result in interactions in the future. To overcome these limitations, we propose a novel multimedia recommendation framework, named STARLINE, utilizing contraSTive leARning with modaLIty-aware graph refiNEment. Extensive experiments on five real-world datasets validate the effectiveness and validity of STARLINE, especially showing consistently higher accuracy by up to 13.24% compared to the best competitor.

The problem of career trajectory prediction (CTP) aims to predict one's future employer or job position. While several CTP methods have been developed for this problem, we posit that none of these methods (1) jointly considers the mutual ternary dependency between three key units (i.e., user, position, and company) of a career and (2) captures the characteristic shifts of key units in career over time, leading to an inaccurate understanding of the job movement patterns in the labor market. To address the above challenges, we propose a novel solution, named as CAPER, that solves the challenges via sophisticated temporal knowledge graph (TKG) modeling. It enables the utilization of a graph-structured knowledge base with rich expressiveness, effectively preserving the changes in job movement patterns. Furthermore, we devise an extrapolated career reasoning task on TKG for a realistic evaluation. The experiments on a real-world career trajectory dataset demonstrate that CAPER consistently and significantly outperforms four baselines, two recent TKG reasoning methods, and five state-of-the-art CTP methods in predicting one's future companies and positions--i.e., on average, yielding 6.80% and 34.58% more accurate predictions, respectively. The codebase of CAPER is available at https://github.com/Bigdasgit/CAPER.

Recently, searching for information by using search engines such as Google, Bing, and NAVER has become ubiquitous. While they attempt to provide information based on the search queries that users enter, it is not trivial to accurately capture the search intent of users. Motivated by this situation, NAVER Corp., the largest portal company in Korea, has developed a framework named as CATER (Cluster-based Alternative TErm Recommendation) framework that suggests alternative terms ("al-terms,'' in short) for better search outcomes relevant to a user's search intent. We introduce four design considerations (DCs) that were considered when designing and implementing CATER. Then, we describe how our CATER addresses the four DCs by using a clustering stage that dynamically maintains a pool of topic-oriented clusters containing terms, and a recommendation stage that identifies the top-k clusters (i.e., topics) and the top-k al-terms for each cluster. Furthermore, we present the scalable architecture adopted by CATER. Through various offline and online A/B tests using real-world datasets from NAVER, we validate that CATER successfully incorporates all DCs and that all design choices help improve the recommendation accuracy.

Recent works in multimodal recommendations, which leverage diverse modal information to address data sparsity and enhance recommendation accuracy, have garnered considerable interest. Two key processes in multimodal recommendations are modality fusion and representation learning. Previous approaches in modality fusion often employ simplistic attentive or pre-defined strategies at early or late stages, failing to effectively handle irrelevant information among modalities. In representation learning, prior research has constructed heterogeneous and homogeneous graph structures encapsulating user-item, user-user, and item-item relationships to better capture user interests and item profiles. Modality fusion and representation learning were considered as two independent processes in previous work. This paper reveals that these two processes are complementary and can support each other. Specifically, powerful representation learning enhances modality fusion, while effective fusion improves representation quality. Stemming from these two processes, we introduce a COmposite grapH convolutional nEtwork with dual-stage fuSION for the multimodal recommendation, named COHESION. Specifically, it introduces a dual-stage fusion strategy to reduce the impact of irrelevant information, refining all modalities using behavior modality in the early stage and fusing their representations at the late stage. It also proposes a composite graph convolutional network that utilizes user-item, user-user, and item-item graphs to extract heterogeneous and homogeneous latent relationships within users and items. Besides, it introduces a novel adaptive optimization to ensure balanced and reasonable representations across modalities. Extensive experiments on three public datasets demonstrate the significant superiority of COHESION over various competitive baselines.

Existing multimedia recommender systems have made the best efforts to predict user preferences for items by utilizing behavioral similarities between users and the modality features of items a user has interacted with. However, we identify two key limitations in existing methods regarding preferences for modality features: (L1) although preferences for modality features is an important aspect of users' preferences, existing methods only leverage neighbors with similar interactions and do not consider the neighbors who may have similar preferences for modality features while having different interactions; (L2) although modality features of a user and an item may have a complex geometric relationship in the latent space, existing methods overlook and face challenges in precisely capturing this relationship. To address these two limitations, we propose a novel multimedia recommendation framework, named MELON, which is based on two core ideas: (Idea 1) Modality-cEntered embedding extraction; (Idea 2) reLatiOnship-ceNtered embedding extraction. We validate the effectiveness and validity of MELON through extensive experiments with four real-world datasets, showing 10.51% higher accuracy compared to the best competitor in terms of recall@10. The code and dataset of MELON is available at https://github.com/Bigdasgit/MELON.

The goal of Review-Based Recommendation System (RBRS) is to effectively learn the representations of users and items by utilizing review texts in addition to user-item interactions. From user-item interaction graphs widely employed in recommendation systems, recent RBRS methods using graph neural networks (GNNs) obtain the representations by associating each edge between a user and an item with the review information of the user for that item. However, these GNN-based RBRS methods present two main issues: (1) by con- verting each review text into the weight, i.e., single value, of a edge between a user node and an item node, they lose the rich informa- tion about users and items inherent in the review; and (2) by creating only a single general representation for each user, they cannot repre- sent the individual effects of users' likes and dislikes on their ratings for items they have interacted with. To address these problems, we propose a novel GNN-based RBRS, named LETTER, utilizing homo- geneous graphs, i.e., user-user graphs and an item-item graph, to learn general representations of users and items along with users' like and dislike representations. LETTER can learn user and item representations without losing review information by utilizing the proposed homogeneous graphs. Furthermore, LETTER explicitly designs the influence of users' like and dislike representations on their ratings to perform accurate rating predictions. Through ex- periments on six datasets, we verify that the proposed LETTER out- performs nine state-of-the-art RBRSs by up to 23.1%. Our source code is available at https://github.com/Bigdasgit/LETTER.

In e-commerce platforms, profit-aware recommender systems aim to improve the platform's profits while maintaining high overall accuracy by recommending items with high profits as top-ranked items. We explore two issues faced by existing model-based profit-aware approaches (i.e., MBAs) when training recommendation models for profit enhancement. First, existing MBAs tend to inaccurately infer the item ranking without considering the user's current preference for each item through their profit-based weighting scheme. Second, through the point-wise learning-to-rank (LTR), the model is optimized solely for the preference score of each item independently rather than being directly optimized for the overall ranking of items. To tackle these issues, we propose a novel MBA that involves three key steps: (S1) defining the Current Preference incorporated with Profit (i.e., CPP) for items; (S2) classifying items through CPP; and (S3) training the model by list-wise LTR based on CPP. Extensive experimental results using real-world platform datasets demonstrate that our approach improves accuracy by approximately 4% and profits by about 24% compared to the best-competing method.

Personalized news recommendation aims to assist users in finding news articles that align with their interests, which plays a pivotal role in mitigating users' information overload problem. Despite the breakthrough in personalized news recommendation, the following challenges have been rarely explored: (C1) Comprehending manifold intents coupled within a news article, (C2) Differentiating varying post-read preferences of news articles, and (C3) Addressing the cold-start user problem. To tackle these challenges together, we propose a novel personalized news recommendation framework (CROWN) that employs (1) category-guided intent disentanglement for (C1), (2) consistency-based news representation for (C2), and (3) GNN-enhanced hybrid user representation for (C3). Furthermore, we incorporate a category prediction into the training process of CROWN as an auxiliary task for enhancing intent disentanglement. Extensive experiments on two real-world datasets reveal that (1) CROWN outperforms twelve state-of-the-art news recommendation methods and (2) the proposed strategies significantly improve the accuracy of CROWN.

Hypergraphs can naturally modelgroup-wise relations(e.g., a group of users who co-purchase an item) ashyperedges.Hyperedge predictionis to predict future or unobserved hyperedges, which is a fundamental task in many real-world applications (e.g., group recommendation). Despite the recent breakthrough of hyperedge prediction methods, the following challenges have been rarely studied: (C1)How to aggregate the nodes in each hyperedge candidate for accurate hyperedge prediction?and (C2)How to mitigate the inherent data sparsity problem in hyperedge prediction?To tackle both challenges together, in this paper, we propose a novel hyperedge prediction framework ($\mathsf{CASH}$CASH) that employs (1)context-aware node aggregationto precisely capture complex relations among nodes in each hyperedge for (C1) and (2)self-supervised contrastive learningin the context of hyperedge prediction to enhance hypergraph representations for (C2). Furthermore, as for (C2), we propose ahyperedge-aware augmentationmethod to fully exploit the latent semantics behind the original hypergraph and consider both node-level and group-level contrasts (i.e.,dual contrasts) for better node and hyperedge representations. Extensive experiments on six real-world hypergraphs reveal that$\mathsf{CASH}$consistently outperforms all competing methods in terms of the accuracy in hyperedge prediction and each of the proposed strategies is effective in improving the model accuracy of$\mathsf{CASH}$.

The goal of dynamic signed network embedding (DSNE) is to represent the nodes in a dynamic signed network (DSN) as embeddings that preserve the evolving nature of conflicting relationships between nodes. While existing DSNE methods are useful for understanding polarization between users in diverse domains, they fail to consider the concept of a community boundary that contributes to network-wide polarization and lack inductive ability due to their reliance on homophily bias. To address these limitations, we propose a novel DSNE method, named PolarDSN, which learns the evolution of network POLARization and enhances inductive ability for Dynamic Signed Networks. It leverages node-level community boundaries as well as structural characteristics of nodes such as structural isomorphism and temporal transitivity. Experiments on four real-world DSN datasets demonstrate that PolarDSN consistently and significantly outperforms 12 state-of-the-art methods, achieving up to 31.6% and 21.1% improvement in macro-F1 for transductive and inductive settings, respectively. The code is available at https://github.com/kmj0792/PolarDSN.

The Fair Graph Anomaly Detection (FairGAD) problem aims to accurately detect anomalous nodes in an input graph while avoiding biased predictions against individuals from sensitive subgroups. However, the current literature does not comprehensively discuss this problem, nor does it provide realistic datasets that encompass actual graph structures, anomaly labels, and sensitive attributes. To bridge this gap, we introduce a formal definition of the FairGAD problem and present two novel datasets constructed from the social media platforms Reddit and Twitter. These datasets comprise 1.2 million and 400,000 edges associated with 9,000 and 47,000 nodes, respectively, and leverage political leanings as sensitive attributes and misinformation spreaders as anomaly labels. We demonstrate that our FairGAD datasets significantly differ from the synthetic datasets used by the research community. Using our datasets, we investigate the performance-fairness trade-off in nine existing GAD and non- graph AD methods on five state-of-the-art fairness methods. Code and datasets are available at https://github.com/nigelnnk/FairGAD.

With the prevalence of social media platforms, accurately identifying the same users across different networks through network alignment has become crucial. Existing methods often struggle due to sparse or absent user-identifiable information (node attributes), highlighting the need for augmenting node attributes. However, research on attribute augmentation remains largely under-explored. In this study, we aim to design augmented attributes that enhance network alignment by reflecting three key structural C haracteristics: (C1) global structural characteristic, reflects the global network structure; (C2) seed-based structural characteristic, leverages cross-network structural information associated with seed nodes; (C3) multi-aspect structural characteristic, employs diverse structural relationship measures. To this end, we propose a novel approach for designing trustworthy Augmented Seed-baSed and multI-aspect STructurAl iNformaTion (ASSISTANT) attributes. To enhance alignment performance, we also present a learning module that utilizes a gate mechanism to select the most effective measure dynamically. Extensive experiments across various datasets demonstrate the following: 1) Our network alignment framework, which includes a gate mechanism module, significantly outperforms state-of-the-art methods in alignment accuracy; 2) other state-of-the-art methods using ASSISTANT attributes as input substantially boosts their own alignment accuracy; and 3) using only ASSISTANT attributes without any training process also leads to effective alignment, showcasing their high trustworthiness.

Traffic speed prediction is a crucial task for optimizing navigation systems and reducing traffic congestion. Although there have been efforts to improve the accuracy of speed prediction by incorporating auxiliary features, such as traffic flow, weather, and time, types of auxiliary features are limited and their detailed relationships with speed have not been explored yet. In our study, we present the individual spatio-temporal (IST) dependencies on flow and speed, and characterize three types of IST-dependencies with the flow-to-flow, speed-to-speed, and flow-to-speed graphs. Then, we propose Auxiliary feature-aided Attention Network (ARIAN), a novel approach to judiciously learning the degrees of IST-dependencies with the three graphs and predicting the future speed by leveraging various auxiliary features. Through comprehensive experiments using 3 real-world datasets, we validate the superiority of ARIAN over 10 state-of-the-art methods and the effectiveness of each auxiliary feature and each dependency learner in ARIAN.

In this paper, we focus on multimedia recommender systems using graph convolutional networks (GCNs) where the multimodal features as well as user-item interactions are employed together. Our study aims to exploit multimodal features more effectively in order to accurately capture users' preferences for items. To this end, we point out following two limitations of existing GCN-based multimedia recommender systems: (L1) although multimodal features of interacted items by a user can reveal her preferences on items, existing methods utilize GCN designed to focus only on capturing collaborative signals, resulting in insufficient reflection of the multimodal features in the final user/item embeddings; (L2) although a user decides whether to prefer the target item by considering its multimodal features, existing methods represent her as only a single embedding regardless of the target item's multimodal features and then utilize her embedding to predict her preference for the target item. To address the above issues, we propose a novel multimedia recommender system, named MONET, composed of following two core ideas: modality-embracing GCN (MeGCN) and target-aware attention. Through extensive experiments using four real-world datasets, we demonstrate i) the significant superiority of MONET over seven state-of-the-art competitors (up to 30.32% higher accuracy in terms of recall@20, compared to the best competitor) and ii) the effectiveness of the two core ideas in MONET. All MONET codes are available at https://github.com/Kimyungi/MONET.

To recommend the points of interest (POIs) that a user would check-in next, most deep-learning (DL)-based existing studies have employed random negative (RN) sampling during model training. In this paper, we claim and validate that, as the training proceeds, such an RN sampling in reality performs as sampling easy negative (EN) POIs (i.e., EN sampling) that a user was highly unlikely to check-in at her check-in time point. Furthermore, we verify that EN sampling is more disadvantageous in improving the accuracy than sampling hard negative (HN) POIs (i.e., HN sampling) that a user was highly likely to check-in. To address this limitation, we present the novel concept of the Degree of Positiveness (DoP), which can be formulated by two factors: (i) the degree to which a POI has the characteristics preferred by a user; (ii) the geographical distance between a user and a POI. Then, we propose a new model-training scheme based on HN sampling by using DoP. Using real-world datasets (i.e., NYC, TKY, and Brightkite), we demonstrate that all the state-of-the-art models trained by our scheme showed dramatic improvements in accuracy by up to about 82.8%.

In this paper, we first define information loss that occurs in the hypergraph expansion and then propose a novel framework, named MILEAGE, to evaluate hypergraph expansion methods by measuring their degree of information loss. MILEAGE employs the following four steps: (1) expanding a hypergraph; (2) performing the unsupervised representation learning on the expanded graph; (3) reconstructing a hypergraph based on vector representations obtained; and (4) measuring MILEAGE-score (i.e., mileage) by comparing the reconstructed and the original hypergraphs. To demonstrate the usefulness of MILEAGE, we conduct experiments via downstream tasks on three levels (i.e., node, hyperedge, and hypergraph): node classification, hyperedge prediction, and hypergraph classification on eight real-world hypergraph datasets. Through the extensive experiments, we observe that information loss through hypergraph expansion has a negative impact on downstream tasks and MILEAGE can effectively evaluate hypergraph expansion methods through the information loss and recommend a new method that resolves the problems of existing ones.

The problem of representing nodes in a signed network as low-dimensional vectors, known as signed network embedding (SNE), has garnered considerable attention in recent years. While several SNE methods based on graph convolutional networks (GCNs) have been proposed for this problem, we point out that they significantly rely on the assumption that the decades-old balance theory always holds in the real-world. To address this limitation, we propose a novel GCN-based SNE approach, named as TrustSGCN, which corrects for incorrect embedding propagation in GCN by utilizing the trustworthiness on edge signs for high-order relationships inferred by the balance theory. The proposed approach consists of three modules: (M1) generation of each node’s extended ego-network; (M2) measurement of trustworthiness on edge signs; and (M3) trustworthiness-aware propagation of embeddings. Specifically, TrustSGCN leverages topological information to measure trustworthiness on edge sign for high-order relationships inferred by balance theory. It then considers structural properties inherent to an input network, such as the ratio of triads, to correct for incorrect embedding propagation. Furthermore, TrustSGCN learns the node embeddings by leveraging two well-known social theories, i.e., balance and status, to jointly preserve the edge sign and direction between nodes connected by existing edges in the embedding space. The experiments on six real-world signed network datasets demonstrate that TrustSGCN consistently outperforms six state-of-the-art GCN-based SNE methods. The code is available at https://github.com/kmj0792/TrustSGCN .

Double-vector embedding methods capture the asymmetric information in directed graphs first, and then preserve them in the embedding space by providingtwo latent vectors, i.e., source and target, per node. Although these methods are known to besuperior to the single-vector ones (i.e., providing asingle latent vector per node), wepoint out their three drawbacks as inability to preserve asymmetry on NU-paths, inability to preserve global nodes similarity, and impairing in/out-degree distributions. To address these, we first proposeCRW, anovel similarity measure for graphs that considers contributions ofboth in-links and out-links in similarity computation,without ignoring their directions. Then, we proposeELTRA, aneffective double-vector embedding method to preserve asymmetric information in directed graphs. ELTRA computesasymmetry preserving proximity scores (AP-scores) by employing CRW in which the contribution of out-links and in-links in similarity computation isupgraded anddowngraded, respectively. Then, for every node u, ELTRA selects its top-tclosest nodes based on AP-scores andconforms theranks of their corresponding target vectors w.r.t u's source vector in the embedding space to theiroriginal ranks. Our extensive experimental results withseven real-world datasets andsixteen embedding methods show that (1) CRWsignificantly outperforms Katz and RWR in computing nodes similarity in graphs, (2) ELTRAoutperforms the existing state-of-the-art methods in graph reconstruction, link prediction, and node classification tasks.

Sparse generalized matrix-matrix multiplication (SpGEMM) is a fundamental operation for real-world network analysis. With the increasing size of real-world networks, the single-machine-based SpGEMM approach cannot perform SpGEMM on large-scale networks, exceeding the size of main memory (i.e., not scalable). Although the distributed-system-based approach could handle large-scale SpGEMM based on multiple machines, it suffers from severe inter-machine communication overhead to aggregate results of multiple machines (i.e., not efficient). To address this dilemma, in this paper, we propose a novel storage-based SpGEMM approach (SAGE) that stores given networks in storage (e.g., SSD) and loads only the necessary parts of the networks into main memory when they are required for processing via a 3-layer architecture. Furthermore, we point out three challenges that could degrade the overall performance of SAGE and propose three effective strategies to address them: (1) block-based workload allocation for balancing workloads across threads, (2) in-memory partial aggregation for reducing the amount of unnecessarily generated storage-memory I/Os, and (3) distribution-aware memory allocation for preventing unexpected buffer overflows in main memory. Via extensive evaluation, we verify the superiority of SAGE over existing SpGEMM methods in terms of scalability and efficiency.

As the number of TV shows increases, designing recommendation systems to provide users with their favorable TV shows becomes more important. In a TV show domain, watching a TV show (i.e., giving implicit feedback to the show) among the TV shows broadcast at the same time frame implies that the currently watching show is the winner in the competition with others (i.e., losers). However, in previous studies, such a notion of limited competitions has not been considered in estimating the user’s preferences for TV shows. In this paper, we propose a new recommendation framework to take this new notion into account based on pair-wise models. Our framework is composed of the following ideas: (i) identify winners and losers by determining pairs of competing TV shows; (ii) learn the pairs of competing TV shows based on the confidence for the pair-wise preference between the winner and the loser; (iii) recommend the most favorable TV shows by considering the time factors with respect to users and TV shows. Using a real-world TV show dataset, our experimental results show that our proposed framework consistently improves the accuracy of recommendation by up to 38%, compared with the best state-of-the-art method. The code and datasets of our framework are available in an external link (https://github.com/hongkyun-bae/tvshow_rs).

Sparse general matrix-matrix multiplication (SpGEMM) is a major kernel in various emerging applications, such as database management systems, deep learning, graph analysis, and recommendation systems. Since SpGEMM requires extensive computation, many SpGEMM techniques have been implemented based on graphics processing units (GPUs) to exploit massive data parallelism completely. However, traditional SpGEMM techniques usually do not fully utilize the GPU because most non-zero elements of the target sparse matrices exist in a few hub nodes, and non-hub nodes barely have non-zero elements. The data-related characteristics (power law) result in a significant degradation in performance because of the load imbalance between the GPU cores and the low utilization of each core. Many attempts have been made through recent implementations to solve this problem using smart pre-/post-processing. However, the net performance hardly improves and sometimes even deteriorates owing to the large overheads. Additionally, non-hub nodes are inherently not suitable for GPU computing, even after optimization. Furthermore, the performance is no longer dominated by kernel execution, but by data transfers such as device-to-host (D2H) data transfers and file I/Os, owing to the rapid growth in the computing power of GPUs and input data size.Therefore, this work proposes a Dynamic Block Distributor (DBD), a novel full-system-level SpGEMM orchestration framework for heterogeneous systems, improving the overall performance by enabling an efficient CPU-GPU collaboration and further minimizing the overhead in data transfer between all the system elements. This framework first divides the target matrix into smaller blocks and then offloads the computation of each block to an appropriate computing unit between a GPU and CPU based on its workload type and the status of resource utilization at runtime. It also minimizes the overhead in data transfer with simple but suitable techniques, such as Row Collecting, I/O Overlapping, and I/O Binding. Our experiments showed that this framework increased the execution latency of SpGEMM, which included both the kernel execution and D2H transfers, by 3.24x on average, and the overall execution time by 2.07x on average, compared to that of the baseline cuSPARSE library.

For high-quality conversational recommender systems (CRS), it is important to recommend the suitable items by capturing the items' features mentioned in the dialog and to explain the appropriate ones among the various features of the recommended item. We argue that the CRS model should be a domain-expert who is (1) knowledgeable about the relationships between items and their various features and (2) able to explain the recommended item with its features relevant to dialog context. To this end, we propose a novel framework, named as LATTE, to pre-train each core module in CRS (i.e., the recommendation and the conversation module) through abundant external data. For the recommendation module, we pre-train the recommendation module to comprehensively understand the relationships between items and their various features by leveraging both multi-reviews and a knowledge graph. For pre-training the conversation module, we create the synthetic dialogs, which contain responses providing the explanation relevant to the dialog context by using all the items' features and dialog templates. Through extensive experiments on two public CRS datasets, we demonstrate that LATTE exhibits (1) the effectiveness of each module in LATTE, (2) the superiority over 7 state-of-the art methods, and (3) the interpretations based on visualization.

The problem of signed network embedding (SNE) aims to represent nodes in a given signed network as low-dimensional vectors. While several SNE methods based on graph convolutional networks (GCN) have been proposed, we point out that they significantly rely on the assumption that the decades-old balance theory always holds in the real world. To address this limitation, we propose a novel GCN-based SNE approach, named as TrustSGCN, which measures the trustworthiness on edge signs for high-order relationships inferred by balance theory and corrects incorrect embedding propagation based on the trustworthiness. The experiments on four real-world signed network datasets demonstrate that TrustSGCN consistently outperforms five state-of-the-art GCN-based SNE methods. The code is available at https://github.com/kmj0792/TrustSGCN.

Similarity-based embedding methods have introduced a new perspective on graph embedding by conforming the similarity distribution of latent vectors in the embedding space to that of nodes in the graph; they show significant effectiveness over conventional embedding methods in various machine learning tasks. In this paper, we first point out the three drawbacks of existing similarity-based embedding methods: inaccurate similarity computation, conflicting optimization goal, and impairing in/out-degree distributions. Then, motivated by these drawbacks, we propose AdaSim*, a novel similarity measure for graphs that is conducive to the similarity-based graph embedding. We finally propose GELTOR, an effective embedding method that employs AdaSim* as a node similarity measure and the concept of learning-to-rank in the embedding process. Contrary to existing methods, GELTOR does not learn the similarity scores distribution; instead, for any target node, GELTOR conforms the ranks of its top-t similar nodes in the embedding space to their original ranks based on AdaSim* scores. We conduct extensive experiments with six real-world datasets to evaluate the effectiveness of GELTOR in graph reconstruction, link prediction, and node classification tasks. Our experimental results show that (1) AdaSim* outperforms AdaSim, RWR, and MCT in computing nodes similarity in graphs, (2) our GETLOR outperforms existing state-of-the-arts and conventional embedding methods in most cases of the above machine learning tasks, thereby implying that learning-to-rank is beneficial to graph embedding.

The political stance prediction for news articles has been widely studied to mitigate the echo chamber effect – people fall into their thoughts and reinforce their pre-existing beliefs. The previous works for the political stance problem focus on (1) identifying political factors that could reflect the political stance of a news article and (2) capturing those factors effectively. Despite their empirical successes, they are not sufficiently justified in terms of how effective their identified factors are in the political stance prediction. Motivated by this, in this work, we conduct a user study to investigate important factors in political stance prediction, and observe that the context and tone of a news article (implicit) and external knowledge for real-world entities appearing in the article (explicit) are important in determining its political stance. Based on this observation, we propose a novel knowledge-aware approach to political stance prediction (KHAN), employing (1) hierarchical attention networks (HAN) to learn the relationships among words and sentences in three different levels and (2) knowledge encoding (KE) to incorporate external knowledge for real-world entities into the process of political stance prediction. Also, to take into account the subtle and important difference between opposite political stances, we build two independent political knowledge graphs (KG) (i.e., KG-lib and KG-con) by ourselves and learn to fuse the different political knowledge. Through extensive evaluations on three real-world datasets, we demonstrate the superiority of KHAN in terms of (1) accuracy, (2) efficiency, and (3) effectiveness.

The goal of directed network embedding is to represent the nodes in a given directed network as embeddings that preserve the asymmetric relationships between nodes. While a number of directed network embedding methods have been proposed, we empirically show that the existing methods lack out-of-distribution generalization abilities against degree-related distributional shifts. To mitigate this problem, we propose ODIN (Out-of-Distribution Generalized Directed Network Embedding), a new directed NE method where we model multiple factors in the formation of directed edges. Then, for each node, ODIN learns multiple embeddings, each of which preserves its corresponding factor, by disentangling interest factors and biases related to in- and out-degrees of nodes. Our experiments on four real-world directed networks demonstrate that disentangling multiple factors enables ODIN to yield out-of-distribution generalized embeddings that are consistently effective under various degrees of shifts in degree distributions. Specifically, ODIN universally outperforms 9 state-of-the-art competitors in 2 LP tasks on 4 real-world datasets under both identical distribution (ID) and non-ID settings. The code is available at https://github.com/hsyoo32/odin.

In this article, we propose a framework for embedding-based community detection on signed networks, namelyAdversarial learning ofBalanced triangle forCommunity detection, in short${{\sf ABC}}$. It first represents all the nodes of a signed network as vectors in low-dimensional embedding space and conducts a clustering algorithm (e.g.,k-means) on vectors, thereby detecting a community structure in the network. When performing the embedding process,${{\sf ABC}}$learns only the edges belonging to balanced triangles whose edge signs follow the balance theory, significantly excluding noise edges in learning. To address the sparsity of balanced triangles in a signed network,${{\sf ABC}}$learns not only the edges in balancedreal-triangles but those in balancedvirtual-triangles that do not actually exist but are produced by our generator. Finally,${{\sf ABC}}$employs adversarial learning to generate more-realistic balanced virtual-triangles with less noise edges. Through extensive experiments using seven real-world networks, we validate the effectiveness of (1) learning edges belonging to balanced real/virtual-triangles and (2) employing adversarial learning for signed network embedding. We show that${{\sf ABC}}$consistently and significantly outperforms the state-of-the-art community detection methods in all datasets.

A graph, consisting of vertices and edges, has been widely adopted for network analysis. Recently, with the increasing size of real-world networks, many graph engines have been studied to efficiently process large-scale real-world graphs. RealGraph, one of the state-of-the-art single-machine-based graph engines, efficiently processes storage-to-memory I/Os by considering unique characteristics of real-world graphs. Via an in-depth analysis of RealGraph, however, we found that there is still a chance for more performance improvement in the computation part of RealGraph despite its great I/O processing ability. Motivated by this, in this paper, we propose RealGraphGPU, a GPU-based single-machine graph engine. We design the core components required for GPU-based graph processing and incorporate them into the architecture of RealGraph. Further, we propose two optimizations that successfully address the technical issues that could cause the performance degradation in the GPU-based graph engine: buffer pre-checking and edge-based workload allocation strategies. Through extensive evaluation with 6 real-world datasets, we demonstrate that (1) RealGraphGPU improves RealGraph by up to 546%, (2) RealGraphGPU outperforms existing state-of-the-art graph engines dramatically, and (3) the optimizations are all effective in large-scale graph processing.

This paper focuses on the problem of forecasting daily traffic of new roads, where very little data is available for prediction. We propose a novel prediction model based on Generative Adversarial Networks (GAN) that learns the subtle patterns of the changes in the traffic flow according to the various contextual factors. Then the trained generator makes a prediction via generating a realistic traffic flow data of a target new road given its weather and day type. Both the quantitative and qualitative results of our extensive experiments indicate the effectiveness of our method.

In a news recommender system, a user tends to click on a news article if she is interested in its topic understood by looking at its title. Such a behavior is possible since, when viewing the title, humans naturally think of the contextual meaning of each title word by leveraging their own background knowledge. Motivated by this, we propose a novel personalized news recommendation framework CAST (Context-aware Attention network with a Selection module for Title word representation), which is capable of enriching title words by leveraging body text that fully provides the whole content of a given article as the context. Through extensive experiments, we demonstrate (1) the effectiveness of core modules in CAST, (2) the superiority of CAST over 9 state-of-the-art news recommendation methods, and (3) the interpretability with CAST.

We address the multimedia recommendation problem, which utilizes items' multimodal features, such as visual and textual modalities, in addition to interaction information. While a number of existing multimedia recommender systems have been developed for this problem, we point out that none of these methods individually capture the influence of each modality at the interaction level. More importantly, we experimentally observe that the learning procedures of existing works fail to preserve the intrinsic modality-specific properties of items. To address above limitations, we propose an accurate multimedia recommendation framework, named MARIO, based on modality-aware attention and modality-preserving decoders. MARIO predicts users' preferences by considering the individual influence of each modality on each interaction while obtaining item embeddings that preserve the intrinsic modality-specific properties. The experiments on four real-life datasets demonstrate that MARIO consistently and significantly outperforms seven competitors in terms of the recommendation accuracy: MARIO yields up to 14.61% higher accuracy, compared to the best competitor.

Spatio-temporal models, which combine GNNs (Graph Neural Networks) and RNNs (Recurrent Neural Networks), have shown state-of-the-art accuracy in traffic speed prediction. However, we find that they consider the spatial and temporal dependencies between speeds separately in the two (i.e., space and time) dimensions, thereby unable to exploit the joint-dependencies of speeds in space and time. In this paper, with the evidence via preliminary analysis, we point out the importance of considering individual dependencies between two speeds from all possible points in space and time for accurate traffic speed prediction. Then, we propose an Individual Spatio-Temporal graph (IST-graph) that represents the Individual Spatio-Temporal dependencies (IST-dependencies) very effectively and a Spatio-Temporal Graph ATtention network (ST-GAT), a novel model to predict the future traffic speeds based on the IST-graph and the attention mechanism. The results from our extensive evaluation with five real-world datasets demonstrate (1) the effectiveness of the IST-graph in modeling traffic speed data, (2) the superiority of ST-GAT over 5 state-of-the-art models (i.e., 2-33% gains) in prediction accuracy, and (3) the robustness of our ST-GAT even in abnormal traffic situations.

Many global automakers strive to develop technologies towards the next-generation of intelligent transportation systems (ITS). One of the primary goals of ITS is predicting future traffic speeds to optimize a driver's route, which can lead to not only alleviating traffic flow but also increasing user satisfaction with an ITS service. While prior studies have applied deep learning models to traffic speed prediction and improved model performance, existing models did not well capture abrupt speed changes. In this paper, we propose a novel model, named as adversarial prediction of traffic speed (APOTS), based on adversarial training, data augmentation, and hybrid deep learning modeling. Through the experiments with real traffic data provided by Hyundai Motor Company, we demonstrate that APOTS effectively learns dynamics of traffic speed changes and predicts traffic speed up to 40% higher in accuracy than existing prediction models.

Online news providers such as Google News, Bing News, and NAVER News collect a large number of news articles from a variety of presses and distribute these articles to users via their portals. Dynamic nature of a news domain causes the problem of information overload that makes it difficult for a user to find her preferable news articles. Motivated by this situation, NAVER Corp., the largest portal company in South Korea, identified four design considerations (DCs) for news recommendation that reflect the unique characteristics of a news domain. In this paper, we introduce a large-scale news recommender system named as AiRS, present how it jointly leverages the four DCs for NAVER News service. Specifically, AiRS first generates candidate articles for recommendation to a target user based on collaborative filtering (CF), quality estimation (QE), and social impact (SI) models; then, it ranks the candidate articles based on the scores computed by considering their multi-type feature scores (e.g., user's section preference and article's recency), finally recommending the top-$k$news articles that a target user is likely to prefer. Also, we present how to build the architecture for online deployment of AiRS at NAVER News. Through extensive offline and online A/B tests using the real-world datasets, we validate that AiRS successfully reflects all of the DCs into the news recommendation process, all design choices employed in AiRS help improve the recommendation accuracy, and AiRS significantly outperforms five state-of-the-art news recommendation approaches in terms of accuracy.

The goal of temporal knowledge graph embedding (TKGE) is to represent the entities and relations in a given temporal knowledge graph (TKG) as low-dimensional vectors (i.e., embeddings), which preserve both semantic information and temporal dynamics of the factual information. In this paper, we posit that the intrinsic difficulty of existing TKGE methods lies in the lack of information in KG snapshots with timestamps, each of which contains the facts that co-occur at a specific timestamp. To address this challenge, we propose a novel self-supervised TKGE approach, THOR (Three-tower grapH cOnvolution netwoRks (GCNs)), which extracts latent knowledge from TKGs by jointly leveraging both temporal and atemporal dependencies between entities and the structural dependency between relations. THOR learns the embeddings of entities and relations Our experiments on three real-world datasets demonstrate that THOR significantly outperforms 13 competitors in terms of TKG completion tasks. The codebase of THOR is available at https://github.com/EJHyun/THOR.

There were fierce debates on whether the non-linear embedding propagation of GCNs is appropriate to GCN-based recommender systems. It was recently found that the linear embedding propagation shows better accuracy than the non-linear embedding propagation. Since this phenomenon was discovered especially in recommender systems, it is required that we carefully analyze the linearity and non-linearity issue. In this work, therefore, we revisit the issues of i) which of the linear or non-linear propagation is better and ii) which factors of users/items decide the linearity/non-linearity of the embedding propagation. We propose a novel Hybrid method of linear and non-linear collaborative filtering method (HMLET, pronounced as Hamlet). In our design, there exist both linear and non-linear propagation steps, when processing each user or item node, and our gating module chooses one of them, which results in a hybrid model of the linear and non-linear GCN-based collaborative filtering (CF). The proposed model yields the best accuracy in three public benchmark datasets. Moreover, we classify users/items into the following three classes depending on our gating modules' selections: Full-Non-Linearity (FNL), Partial-Non-Linearity (PNL), and Full-Linearity (FL). We found that there exist strong correlations between nodes' centrality and their class membership, i.e., important user/item nodes exhibit more preferences towards the non-linearity during the propagation steps. To our knowledge, we are the first who design a hybrid method and report the correlation between the graph centrality and the linearity/non-linearity of nodes. All HMLET codes and datasets are available at: https://github.com/qbxlvnf11/HMLET.

Explainable recommendation has gained great attention in recent years. A lot of work in this research line has chosen to use the knowledge graphs (KG) where relations between entities can serve as explanations. However, existing studies have not considered sentiment on relations in KG, although there can be various types of sentiment on relations worth considering (e.g., a user's satisfaction on an item). In this paper, we propose a novel recommendation framework based on KG integrated with sentiment analysis for more accurate recommendation as well as more convincing explanations. To this end, we first construct a Sentiment-Aware Knowledge Graph (namely, SAKG) by analyzing reviews and ratings on items given by users. Then, we perform item recommendation and reasoning over SAKG through our proposed Sentiment-Aware Policy Learning (namely, SAPL) based on a reinforcement learning strategy. To enhance the explainability for end-users, we further developed an interactive user interface presenting textual explanations as well as a collection of reviews related with the discovered sentiment. Experimental results on three real-world datasets verified clear improvements on both the accuracy of recommendation and the quality of explanations.

The directed network embedding problem is to represent the nodes in a given directed network as embeddings (i.e., low-dimensional vectors) that preserve the asymmetric relationships between nodes. While a number of approaches have been developed for this problem, we point out that existing approaches commonly face difficulties in accurately preserving asymmetric proximities between nodes in a sparse network containing a large number of low out- and in-degree nodes. In this paper, we focus on addressing this intrinsic difficulty caused by the lack of information. We first introduce the concept of virtual negative edges (VNEs), which represent latent negative relationships between nodes. Based on the concept, we propose a novel DIrected NE approach with VIrtual Negative Edges, named as DIVINE. DIVINE carefully decides the number and locations of VNEs to be added to the input network. Once VNEs are added, DIVINE learns embeddings by exploiting both the signs and directions of edges. Our experiments on four real-world directed networks demonstrate that adding VNEs alleviates the lack of information about low-degree nodes, thereby enabling DIVINE to yield high-quality embeddings that accurately capture asymmetric proximities between nodes. Specifically, the embeddings obtained by DIVINE lead to up to 10.16% more accurate link prediction, compared to those obtained by state-of-the-art competitors.

A large-batch training with data parallelism is a widely adopted approach to efficiently train a large deep neural network (DNN) model. Large-batch training, however, often suffers from the problem of the model quality degradation because of its fewer iterations. To alleviate this problem, in general, learning rate (lr) scaling methods have been applied, which increases the learning rate to make an update larger at each iteration. Unfortunately, however, we observe that large-batch training with state-of-the-art lr scaling methods still often degrade the model quality when a batch size crosses a specific limit, rendering such lr methods less useful. To this phenomenon, we hypothesize that existing lr scaling methods overlook the subtle but important differences across “layers” in training, which results in the degradation of the overall model quality. From this hypothesis, we propose a novel approach (LENA) toward the learning rate scaling for large-scale DNN training, employing: (1) a layer-wise adaptive lr scaling to adjust lr for each layer individually, and (2) a layer-wise state-aware warm-up to track the state of the training for each layer and finish its warm-up automatically. The comprehensive evaluation with variations of batch sizes demonstrates that LENA achieves the target accuracy (i.e., the accuracy of single-worker training): (1) within the fewest iterations across different batch sizes (up to 45.2% fewer iterations and 44.7% shorter time than the existing state-of-the-art method), and (2) for training very large-batch sizes, surpassing the limits of all baselines.

As an emotion plays an important role in people’s everyday lives and is often mirrored in their social media use, extensive research has been conducted to characterize and model emotions from social media data. However, prior research has not sufficiently considered trends of social media use—the increasing use of images and the decreasing use of text—nor identified the features of images in social media that are likely to be different from those in non-social media. Our study aims to fill this gap by (1) considering the notion of visual hints that depict contextual information of images, (2) presenting their characteristics in positive or negative emotions, and (3) demonstrating their effectiveness in emotion prediction modeling through an in-depth analysis of their relationship with the text in the same posts. The results of our experiments showed that our visual hint-based model achieved 20% improvement in emotion prediction, compared with the baseline. In particular, the performance of our model was comparable with that of the text-based model, highlighting not only a strong relationship between visual hints of the image and emotion, but also the potential of using only images for emotion prediction which well reflects current and future trends of social media use.

In the literature, various link-based similarity measures such as Adamic/Adar (in short Ada), SimRank, and random walk with restart (RWR) have been proposed. Contrary to SimRank and RWR, Ada is a non-recursive measure, which exploits the local graph structure in similarity computation. Motivated by Ada's promising results in various graph-related tasks, along with the fact that SimRank is a recursive generalization of the co -citation measure, in this paper, we propose AdaSim, a recursive similarity measure based on the Ada philosophy. Our AdaSim provides identical accuracy to that of Ada on the first iteration and it is applicable to both directed and undirected graphs. To accelerate our iterative form, we also propose a matrix form that is dramatically faster while providing the exact AdaSim scores. We conduct extensive experiments with five real-world datasets to evaluate both the effectiveness and efficiency of our AdaSim in comparison with those of existing similarity measures and graph embedding methods in the task of similarity computation of nodes. Our experimental results show that 1) AdaSim significantly improves the effectiveness of Ada and outperforms other competitors, 2) its efficiency is comparable to that of SimRank* while being better than the others, 3) AdaSim is not sensitive to the parameter tuning, and 4) similarity measures are better than embedding methods to compute similarity of nodes.

To speed up the training of massive deep neural network (DNN) models, distributed training has been widely studied. In general, a centralized training, a type of distributed training, suffers from the communication bottleneck between a parameter server (PS) and workers. On the other hand, a decentralized training suffers from increased parameter variance among workers that causes slower model convergence. Addressing this dilemma, in this work, we propose a novel centralized training algorithm, ALADDIN, employing "asymmetric" communication between PS and workers for the PS bottleneck problem and novel updating strategies for both local and global parameters to mitigate the increased variance problem. Through a convergence analysis, we show that the convergence rate of ALADDIN is O(1 ønk ) on the non-convex problem, where n is the number of workers and k is the number of training iterations. The empirical evaluation using ResNet-50 and VGG-16 models demonstrates that (1) ALADDIN shows significantly better training throughput with up to 191% and 34% improvement compared to a synchronous algorithm and the state-of-the-art decentralized algorithm, respectively, (2) models trained by ALADDIN converge to the accuracies, comparable to those of the synchronous algorithm, within the shortest time, and (3) the convergence of ALADDIN is robust under various heterogeneous environments.

In this paper, we propose a framework for embedding-based community detection on signed networks. It first represents all the nodes of a signed network as vectors in low-dimensional embedding space and conducts a clustering algorithm (e.g., k-means) on vectors, thereby detecting a community structure in the network. When performing the embedding process, our framework learns only the edges belonging to balanced triangles whose edge signs follow the balance theory, significantly excluding noise edges in learning. To address the sparsity of balanced triangles in a signed network, our framework learns not only the edges in balanced real-triangles but those in balanced virtual-triangles that are produced by our generator. Finally, our framework employs adversarial learning to generate more-realistic balanced virtual-triangles with less noise edges. Through extensive experiments using seven real-world networks, we validate the effectiveness of (1) learning edges belonging to balanced real/virtual-triangles and (2) employing adversarial learning for signed network embedding. We show that our framework consistently and significantly outperforms the state-of-the-art community detection methods in all datasets.

In recent years, quantization methods have successfully accelerated the training of large deep neural network (DNN) models by reducing the level of precision in computing operations (e.g., forward/backward passes) without sacrificing its accuracy. In this work, therefore, we attempt to apply such a quantization idea to the popular Matrix factorization (MF) methods to deal with the growing scale of models and datasets in recommender systems. However, to our dismay, we observe that the state-of-the-art quantization methods are not effective in the training of MF models, unlike their successes in the training of DNN models. To this phenomenon, we posit that two distinctive features in training MF models could explain the difference: (i) the training of MF models is much more memory-intensive than that of DNN models, and (ii) the quantization errors across users and items in recommendation are not uniform. From these observations, we develop a quantization framework for MF models, named MASCOT, employing novel strategies (i.e., m-quantization and g-switching) to successfully address the aforementioned limitations of quantization in the training of MF models. The comprehensive evaluation using four real-world datasets demonstrates that MASCOT improves the training performance of MF models by about 45%, compared to the training without quantization, while maintaining low model errors, and the strategies and implementation optimizations of MASCOT are quite effective in the training of MF models. For the detailed information about MASCOT, we release the code of MASCOT and the datasets at: https://github.com/Yujaeseo/lCDM-2021_MASCOT.

In this paper, we address the personalized node ranking (PNR) problem for signed networks, which aims to rank nodes in an order most relevant to a given seed node in a signed network. The recently-proposed PNR methods introduce the concept of the signed random surfer, denoted as SRSurfer, that performs the score propagation between nodes using the balance theory. However, in real settings of signed networks, edge relationships often do not strictly follow the rules of the balance theory. Therefore, SRSurfer-based PNR methods frequently perform incorrect score propagation to nodes, thereby degrading the accuracy of PNR. To address this limitation, we propose a novel random-walk based PNR approach with sign verification, named as OBOE (lOok Before yOu lEap). Specifically, OBOE carefully verifies the score propagation of SRSurfer by using the topological features of nodes. Then, OBOE corrects all incorrect score propagation cases by exploiting the statistics of a given network. The experiments on 3 real-world signed networks show that OBOE consistently and significantly outperforms 5 competing methods with improvement up to 13%, 95%, and 249% in top-k PNR, bottom-k PNR, and troll identification tasks, respectively. All OBOE codes and datasets are available at: http://github.com/wonchang24/OBOE.

In this demo, we present RealGraph Web , a web-based platform that provides various kinds of graph analysis services. RealGraph Web is based on RealGraph, a graph engine that addresses the problem of performance degradation in processing real-world big graphs, achieving great performance improvement up to 44 times over existing state-of-the-art graph engines. RealGraph Web runs on a single machine with a web-based interface, thereby allowing users to easily and conveniently enjoy graph analysis services and perform various graph algorithms anywhere on the web . In this demo, we present how a user can analyze a graph on RealGraph Web in three steps and get the analysis result quickly via a graphical user interface.

In this paper, we present CR-Graph (community reinforcement on graphs), a novel method that helps existing algorithms to perform more-accurate community detection (CD). Toward this end, CR-Graph strengthens the community structure of a given original graph by adding non-existent predicted intra-community edges and deleting existing predicted inter-community edges. To design CR-Graph, we propose the following two strategies: (1) predicting intra-community and inter-community edges (i.e., the type of edges) and (2) determining the amount of edges to be added/deleted. To show the effectiveness of CR-Graph, we conduct extensive experiments with various CD algorithms on 7 synthetic and 4 real-world graphs. The results demonstrate that CR-Graph improves the accuracy of all underlying CD algorithms universally and consistently.

For these few decades malwares have been posing a major concern in the cyber security. Recently, a number of "author groups" have been generating lots of newmalwares by sharing source code within a group and exploiting evasive schemes such as polymorphism and metamorphism. This motivates us to study the problem of identifying the author group of a given malware, which would be able to work for not only blocking malwares but also legally punishing suspected malware authors. In this paper, we propose a human-machine collaborative approach for classifying author groups of malwares accurately. We also propose a visualization method for helping human experts to make the decision easily. We verify the superiority of our framework through extensive experiments using real-world malware data.

In this paper, we start by pointing out the limitations on the validation of existing signed network embedding (NE) methods. To address the limitations, we design the two research questions: (1) are signed NE methods consistently more effective in various types of tasks than unsigned NE methods? (2) in signed NE methods, does the utilization of negative links help provide higher accuracy in various tasks? To answer the questions, we present our evaluation framework consisting of three components: (1) five signed network datasets; (2) six signed and two unsigned NE methods; (3) five types of tasks. Through extensive experiments on our evaluation framework, we demonstrate that additional utilization of negative links really helps only in some tasks related to negative links but not in tasks related to positive links.

As social network services (SNS) are expanding from friend-based to interest-based, users form a new type of relationships, namely interest-based relationships, with friends and others through social activities (e.g., likes, comments). Although such relationships are highlighted in the common-identity theory and have important values in theoretical and practical aspects, little evidence exists in the literature pertaining to the explanation of social activities as a central component for social network analysis and an association with friendship. In this paper, we build like networks in Instagram and analyze them through the lens of two salient aspects - friendship and interest - that constitute social networks. Our study results (1) show ambiguous interpretations of the like activities between users who are friends, based on the comparative analysis between friend- and non-friend-based like networks, and (2) demonstrate strong signals of the hashtag characterizing the interest-based relationships in users and content. Our research substantiates and gives insights on the common-identity theory applied in online social networks through data-driven, empirical analysis.

Sparse matrix multiplication (spGEMM) is widely used to analyze the sparse network data, and extract important information based on matrix representation. As it contains a high degree of data parallelism, many efficient implementations using data-parallel programming platforms such as CUDA and OpenCL have been introduced on graphic processing units (GPUs). Several well-known spGEMM techniques, such as cuS- PARSE and CUSP, often do not utilize the GPU resources fully, owing to the load imbalance between threads in the expansion process and high memory contention in the merge process. Furthermore, even though several outer-product-based spGEMM techniques are proposed to solve the load balancing problem on expansion, they still do not utilize the GPU resources fully, because severe computation load variations exist among the multiple thread blocks.To solve these challenges, this paper proposes a new optimization pass called Block Reorganizer, which balances the total computations of each computing unit on target GPUs, based on the outer-product-based expansion process, and reduces the memory pressure during the merge process. For expansion, it first identifies the actual computation amount for each block, and then performs two thread block transformation processes based on their characteristics: 1) B-Splitting to transform a heavy-computation blocks into multiple small blocks and 2) B- Gathering to aggregate multiple small-computation blocks to a larger block. While merging, it improves the overall performance by performing B-Limiting to limit the number of blocks on each computing unit. Experimental results show that it improves the total performance of kernel execution by 1.43x, on an average, when compared to the row-product-based spGEMM, for NVIDIA Titan Xp GPUs on real-world datasets.

Cold-start problems are arguably the biggest challenges faced by collaborative filtering (CF) used in recommender systems. When few ratings are available, CF models typically fail to provide satisfactory recommendations for cold-start users or to display cold-start items on users' top-N recommendation lists. Data imputation has been a popular choice to deal with such problems in the context of CF, filling empty ratings with inferred scores. Different from (and complementary to) data imputation, this paper presents AR-CF, which stands for Augmented Reality CF, a novel framework for addressing the cold-start problems by generating virtual, but plausible neighbors for cold-start users or items and augmenting them to the rating matrix as additional information for CF models. Notably, AR-CF not only directly tackles the cold-start problems, but is also effective in improving overall recommendation qualities. Via extensive experiments on real-world datasets, AR-CF is shown to (1) significantly improve the accuracy of recommendation for cold-start users, (2) provide a meaningful number of the cold-start items to display in top-N lists of users, and (3) achieve the best accuracy as well in the basic top-N recommendations, all of which are compared with recent state-of-the-art methods.

Motivated by a success of generative adversarial networks (GAN) in various domains including information retrieval, we propose a novel signed network embedding framework, ASiNE, which represents each node of a given signed network as a low-dimensional vector based on the adversarial learning. To do this, we first design a generator G+ and a discriminator D+ that consider positive edges, as well as a generator G - and a discriminator D- that consider negative edges: (1) G+/G- aim to generate the most indistinguishable fake positive/negative edges, respectsupively; (2) D+/D aim to discriminate between real positive/negative edges and fake positive/negative edges, respectively. Furthermore, under ASiNE, we propose two new strategies for effective signed network embedding: (1) an embedding space sharing strategy for learning both positive and negative edges; (2) a fake edge generation strategy based on the balance theory. Through extensive experiments using five real-life signed networks, we verify the effectiveness of each of the strategies employed in ASiNE. We also show that ASiNE consistently and significantly outperforms all the state-of-the-art signed network embedding methods in all datasets and with all metrics in terms of accuracy of sign prediction.

As the number of TV channels increases, it is becoming important to recommend TV shows that users prefer to watch. To this end, we investigate the inherent characteristics of implicit feedback given in the TV show domain, and identify the challenges for building an effective TV show recommendation. Based on the unique characteristics, we define a user's watchable interval, the most important and novel concept in understanding users' true preferences. In order to reflect this new concept into the TV show recommendation, we propose a novel framework based on collaborative filtering. Our framework is composed of (1) preference estimation based on a user's watchable interval, (2) preference prediction based on confidence exploiting watchable episodes, and (3) top-N recommendation considering TV show's staying and remaining times. Using a real-world TV show dataset, we demonstrate that our framework effectively solves the challenges and significantly outperforms other existing state-of-the-art methods.

Generative Adversarial Networks (GAN) have not only achieved a big success in various generation tasks such as images, but also boosted the accuracy of classification tasks by generating additional labeled data, which is called data augmentation. In this paper, we propose a Rating Augmentation framework with GAN, named RAGAN, aiming to alleviate the data sparsity problem in collaborative filtering (CF), eventually improving recommendation accuracy significantly. We identify a unique challenge that arises when applying GAN to CF for rating augmentation: naive RAGAN tends to generate values biased towards high ratings. Then, we propose a refined version of RAGAN, named RAGANBT, which addresses this challenge successfully. Via our extensive experiments, we validate that our RAGANBT is really effective to solve the data sparsity problem, thereby providing existing CF models with great improvement in accuracy under various situations such as basic top-N recommendation, long-tail item recommendation, and recommendation to cold-start users.

As the size of real-world graphs has drastically increased in recent years, a wide variety of graph engines have been developed to deal with such big graphs efficiently. However, the majority of graph engines have been designed without considering the power-law degree distribution of real-world graphs seriously. Two problems have been observed when existing graph engines process real-world graphs: inefficient scanning of the sparse indicator and the delay in iteration progress due to uneven workload distribution. In this paper, we propose RealGraph, a single-machine based graph engine equipped with the hierarchical indicator and the block-based workload allocation. Experimental results on real-world datasets show that RealGraph significantly outperforms existing graph engines in terms of both speed and scalability.

We develop a novel framework, named as$l$-injection, to address the sparsity problem of recommender systems. By carefully injecting low values to a selected set of unrated user-item pairs in a user-item matrix, we demonstrate that top-Nrecommendation accuracies of various collaborative filtering (CF) techniques can be significantly and consistently improved. We first adopt the notion ofpre-use preferencesof users toward a vast amount ofunrateditems. Using this notion, we identifyuninterestingitems that have not been rated yet but are likely to receive low ratings from users, and selectively impute them as low values. As our proposed approach is method-agnostic, it can be easily applied to a variety of CF algorithms. Through comprehensive experiments with three real-life datasets (e.g., Movielens, Ciao, and Watcha), we demonstrate that our solution consistently and universally enhances the accuracies of existing CF algorithms (e.g., item-based CF, SVD-based CF, and SVD++) by 2.5 to 5 times on average. Furthermore, our solution improves the running time of those CF methods by 1.2 to 2.3 times when its setting produces the best accuracy. The datasets and codes that we used in the experiments are available at:https://goo.gl/KUrmip.

Generative Adversarial Networks (GAN) have achieved big success in various domains such as image generation, music generation, and natural language generation. In this paper, we propose a novel GAN-based collaborative filtering (CF) framework to provide higher accuracy in recommendation. We first identify a fundamental problem of existing GAN-based methods in CF and highlight it quantitatively via a series of experiments. Next, we suggest a new direction of vector-wise adversarial training to solve the problem and propose our GAN-based CF framework, called CFGAN, based on the direction. We identify a unique challenge that arises when vector-wise adversarial training is employed in CF. We then propose three CF methods realized on top of our CFGAN that are able to address the challenge. Finally, via extensive experiments on real-world datasets, we validate that vector-wise adversarial training employed in CFGAN is really effective to solve the problem of existing GAN-based CF methods. Furthermore, we demonstrate that our proposed CF methods on CFGAN provide recommendation accuracy consistently and universally higher than those of the state-of-the-art recommenders.

Data sparsity is one of the biggest problems faced by collaborative filtering used in recommender systems. Data imputation alleviates the data sparsity problem by inferring missing ratings and imputing them to the original rating matrix. In this paper, we identify the limitations of existing data imputation approaches and suggest three new claims that all data imputation approaches should follow to achieve high recommendation accuracy. Furthermore, we propose a deep-learning based approach to compute imputed values that satisfies all three claims. Based on our hypothesis that most pre-use preferences (e.g., impressions) on items lead to their post-use preferences (e.g., ratings), our approach tries to understand via deep learning how pre-use preferences lead to post-use preferences differently depending on the characteristics of users and items. Through extensive experiments on real-world datasets, we verify our three claims and hypothesis, and also demonstrate that our approach significantly outperforms existing state-of-the-art approaches.

Influence Maximization (IM) is the problem of finding a seed set composed of k nodes that maximize their influence spread over a social network. Kempe et al. showed the problem to be NP-hard and proposed a greedy algorithm (referred to as SimpleGreedy ) that guarantees 63% influence spread of its optimal solution. However, SimpleGreedy has two performance issues: at a micro level , it estimates the influence spread of a single node by running Monte-Carlo (MC) simulations that are fairly expensive; at a macro level, after selecting one seed at each step, it re-evaluates the influence spread of every node in a social network, leading to significant computational overhead. In this paper, we propose Hybrid-IM that addresses the two issues in both micro and macro levels by combining PB-IM (Path Based Influence Maximization) and CB-IM (Community Based Influence Maximization) . Furthermore, we identify two technical issues that could improve the performance of Hybrid-IM more and propose two strategies to address those issues. Through extensive experiments with four real-world datasets, we show that Hybrid-IM achieves great improvement (up to 43 times) in performance over state-of-the-art methods and finds the seed set that provides the influence spread very close to that of the state-of-the-art methods.

With the NAND flash memory technology of solid-state drives (SSDs), the usage of SSDs is expanded to various devices. Due to the cost and time limitations of measuring the actual execution time of each application on SSDs, it is difficult for users to determine the best SSD for their most commonly used applications. In this paper, we propose a framework of estimating the execution time of an application IO trace (i.e., a query IO trace) on a target SSD without its real execution. Our framework is based on the observation that if two IO traces are similar in their IO behavior, their execution times tend to be similar when executed on the same SSD. The performance of the framework is evaluated through extensive experiments on real applications. The results show that our framework is accurate in estimating the execution time of an IO trace on SSDs.

Smart TVs are rapidly replacing conventional TVs. In a number of countries, set-top boxes (STB) are widely used to relay TV channels to smart TVs. In such cases, smart TVs cannot identify which TV channel they are receiving. This situation makes it challenging for smart TVs to provide their users with a variety of personalized services, such as context-aware services and recommendation services. In this paper, we introduce our TV channel matching system that resolves such problems. We propose strategies for scaling-out the matching system and improving its accuracy.

Given "who-trusts/distrusts-whom" information, how can we propagate the trust and distrust? With the appearance of fraudsters in social network sites, the importance of trust prediction has increased. Most such methods use only explicit and implicit trust information (e.g., if Smith likes several of Johnson's reviews, then Smith implicitly trusts Johnson), but they do not consider distrust.

The size of graphs has dramatically increased. Graph engines for a single machine have been emerged to process these graphs efficiently. However, existing engines have overlooked a data locality which is an imperative factor to improve the performance of these engines in the previous literature. In this paper, we show the importance of data locality with graph algorithms by running on graph engines based on a single machine.

In this paper, we propose a crowdsourcing-based approach to solving skyline queries with incomplete data. Our main idea is to leverage crowds to infer the pair-wise preferences between tuples when the values of tuples in some attributes are unknown. Specifically, our proposed solution considers three key factors used in existing crowd-enabled algorithms: (1) minimizing a monetary cost in identifying a crowdsourced skyline by using a dominating set, (2) reducing the number of rounds for latency by parallelizing the questions asked to crowds, and (3) improving the accuracy of a crowdsourced skyline by dynamically assigning the number of crowd workers per question. We evaluate our solution over both simulated and real crowdsourcing using the Amazon Mechanical Turk. Compared to a sort-based baseline method, our solution significantly minimizes the monetary cost, and reduces the number of rounds up to two orders of magnitude. In addition, our dynamic majority voting method shows higher accuracy than both static majority voting method and the existing solution using unary questions.

We study how to improve the accuracy and running time of top-N recommendation with collaborative filtering (CF). Unlike existing works that use mostly rated items (which is only a small fraction in a rating matrix), we propose the notion of pre-use preferences of users toward a vast amount of unrated items. Using this novel notion, we effectively identify uninteresting items that were not rated yet but are likely to receive very low ratings from users, and impute them as zero. This simple-yet-novel zero-injection method applied to a set of carefully-chosen uninteresting items not only addresses the sparsity problem by enriching a rating matrix but also completely prevents uninteresting items from being recommended as top-N items, thereby improving accuracy greatly. As our proposed idea is method-agnostic, it can be easily applied to a wide variety of popular CF methods. Through comprehensive experiments using the Movielens dataset and MyMediaLite implementation, we successfully demonstrate that our solution consistently and universally improves the accuracies of popular CF methods (e.g., item-based CF, SVD-based CF, and SVD++) by two to five orders of magnitude on average. Furthermore, our approach reduces the running time of those CF methods by 1.2 to 2.3 times when its setting produces the best accuracy. The datasets and codes that we used in experiments are available at: https://goo.gl/KUrmip.

In this paper, we propose SimCC-AT (similarity based on content and citations with automatic parameter tuning) to compute the similarity of scientific papers. As in SimCC, the state-of-the-art method, we exploit a notion of a contribution score in similarity computation. SimCC-AT utilizes an automatic weighting scheme based on SVMrank and thus requires only a smaller number of experiments for parameter tuning than SimCC. Furthermore, our experimental results with a real-world dataset show that the accuracy of SimCC-AT is dramatically higher than that of other existing methods and is comparable to that of SimCC.

This paper proposes a novel birthmark, a dynamic API authority vector (DAAV), for detecting software theft. DAAV satisfies four essential requirements for good birthmarks--credibility, resiliency, scalability, and packing-free--while existing birthmarks fail to satisfy all of them together. In particular, existing static birthmarks are unable to handle the packed programs and existing dynamic birthmarks do not satisfy credibility and resiliency. Our experimental results demonstrate that DAAV provides satisfying credibility and resiliency compared with existing dynamic birthmarks and also can cover packed programs.

In this paper, we address how to reduce the amount of page updates in flash-based DBMS equipped with SSD (Solid State Drive). We propose a novel buffering scheme that evicts a dirty page X without flushing it into SSD, and restores the right image of X when X is requested for later access. The restoration of X having previous flushing-less eviction is performed through our online redo actions on X. We call this page-restoring online redo the on-the-fly redo. Although our on-the-fly redo mechanism has some overhead of increasing the number of page reads, this can be compensated by infrequent page updates. Additionally, since the proposed buffering scheme with the on-the-fly redo can easily support the no-steal policy in buffer management, we can enjoy the advantages of smaller logging overhead and faster recovery. Through the TPC-C benchmarks using a Berkeley DB, we show that our scheme shortens the transaction processing times by up to 53%.

As a number of social network services appear online recently, there have been many attempts to analyze social networks for extracting valuable information. Most existing methods first represent a social network as a quite sparse adjacency matrix, and then analyze it through matrix operations such as matrix multiplication. Due to the large scale and high complexity, efficient processing multiplications is an important issue in social network analysis. In this paper, we propose a GPU-based method for efficient sparse matrix multiplication through the parallel computing paradigm. The proposed method aims at balancing the amount of workload both at fine- and coarse-grained levels for maximizing the degree of parallelism in GPU. Through extensive experiments using synthetic and real-world datasets, we show that the proposed method outperforms previous methods by up to three orders-of-magnitude.

This paper introduces the notion of intelligent SSDs. First, we present the design considerations of intelligent SSDs, and then examine their potential benefits under various settings in data mining applications.

As plagiarism of software increases rapidly, there are growing needs for software plagiarism detection systems. In this paper, we propose a software plagiarism detection system using an API-labeled control flow graph (A-CFG) that abstracts the functionalities of a program. The A-CFG can reflect both the sequence and the frequency of APIs, while previous work rarely considers both of them together. To perform a scalable comparison of a pair of A-CFGs, we use random walk with restart (RWR) that computes an importance score for each node in a graph. By the RWR, we can generate a single score vector for an A-CFG and can also compare A-CFGs by comparing their score vectors. Extensive evaluations on a set of Windows applications demonstrate the effectiveness and the scalability of our proposed system compared with existing methods.

In computing the similarity of scientific papers, previous text-based and link-based similarity measures look at only a single side of the content and citations. In this paper, we propose a novel approach called SimCC that effectively combines the content and citation information to accurately compute the similarity of scientific papers. Unlike previous approaches, SimCC effectively represents both authority and context of a scientific paper simultaneously in computing similarities. Also, we propose SimCC+A to consider recently-published papers. The effectiveness of our proposed method is demonstrated via extensive experiments on a real-world dataset of scientific papers, with more than 100% improvement in accuracy compared with previous methods.

In a trust network, two users who are connected by a trust relationship tend to have similar interests. Based on this observation, existing trust-aware recommendation methods predict ratings for a target user on unseen items by referencing to ratings of those users who are reachable from the target user in the forward direction of trustor-trustee relationship through the trust network. However, these methods have overlooked the possibility of utilizing the ratings of those users reachable in the backward direction, which may also have similar interests. In this paper, we investigate this possibility by identifying and adding these users to the existing methods when predicting ratings for the target user. We perform a series of experiments and observe that our approach improves the coverage while preserving the accuracy.

The average of the customer ratings on the product, which we call reputation, is one of the key factors in online purchasing decision of a product. There is, however, no guarantee in the trustworthiness of the reputation since it can be manipulated rather easily. In this paper, we define false reputation as the problem of the reputation to be manipulated by unfair ratings, and design a general framework that provides trustable reputation. For this purpose, we propose TRUEREPUTATION, an algorithm that iteratively adjusts the reputation based on the confidence of customer ratings.

An outlier is an object that is considerably dissimilar with the remainder of the dataset. In this paper, we first propose the notion of centrality and center-proximity as novel outlierness measures which can be considered to represent the characteristics of all of the objects in the dataset. We then propose a graph-based outlier detection method which can solve the problems of local density, micro-cluster, and fringe objects. Finally, through extensive experiments, we show the effectiveness of the proposed method.

The top-n recommendation focuses on finding the top-n items that the target user is likely to purchase rather than predicting his/her ratings on individual items. In this paper, we propose a novel method that provides top-n recommendation by probabilistically determining the target user's preference on items. This method models the purchasing relationships between users and items as a bipartite graph and employs Belief Propagation to compute the preference of the target user on items. We analyze the proposed method in detail by examining the changes in recommendation accuracy under different parameter settings. We also show that the proposed method is up to 40% more accurate than an existing method by comparing it with an RWR-based method via extensive experiments.

A variety of recommendation methods have been proposed to satisfy the performance and accuracy; however, it is fairly difficult to satisfy both of them because there is a trade-off between them. In this paper, we introduce the notion of category experts and propose the recommendation method by exploiting the ratings of category experts instead of those of the users similar to a target user. We also extend the method that uses both the category preference of a target user and his/her similarity to category experts. We show that our method significantly outperforms the existing methods in terms of performance and accuracy through extensive experiments with real-world data.

When a researcher starts with a new topic, it would be very useful if seminal papers in the topic and their relationships are provided in advance. We propose an approach to construct seminal paper genealogy and show the effectiveness and efficiency of our approach.

Color descriptors are one of the important features used in content-based image retrieval. The dominant color descriptor (DCD) represents a few perceptually dominant colors in an image through color quantization. For image retrieval based on DCD, the earth mover's distance and the optimal color composition distance are proposed to measure the dissimilarity between two images. Although providing good retrieval results, both methods are too time-consuming to be used in a large image database. To solve the problem, we propose a new distance function that calculates an approximate earth mover's distance in linear time. To calculate the dissimilarity in linear time, the proposed approach employs the space-filling curve for multidimensional color space. To improve the accuracy, the proposed approach uses multiple curves and adjusts the color positions. As a result, our approach achieves order-of-magnitude time improvement but incurs small errors. We have performed extensive experiments to show the effectiveness and efficiency of the proposed approach. The results reveal that our approach achieves almost the same results with the EMD in linear time.

A blogosphere is a representative example of online social networks. In this paper, we address spectral analysis of a blogosphere. We model a real-world blogosphere as a matrix and a tensor, and then analyze it by using the SVD and PARAFAC decomposition. According to the results, the SVD successfully identified communities, each of which focuses on a specific topic, and also found hub blogs and authoritative posts within each community. The PARAFAC decomposition also succeeded in extracting more communities of finer granules than the SVD. Also, the PARAFAC decomposition could identify the dominant keywords in addition to the hub blogs and authoritative posts honored in each community.

A blog service company provides a function named BlogCast that exposes quality posts on the blog main page to vitalize a blogosphere. This paper analyzes a new type of information diffusion via BlogCast. We show that there exists a strong halo effect in a blogosphere via thorough investigation on a huge volume of blog data.

A group of documents is called near-duplicates if they are almost the same with just a slight difference. Since near-duplicates are major concerns of Web search engines, it is necessary to identify and filter them effectively. Among existing near-duplicate identification methods, MinHashing is the most well-known one. It identifies near-duplicates regardless of locations of different parts in two documents. In blog environment, however, most near-duplicates differ only in their beginning or end. According to our preliminary experiment, about 99% of near-duplicates differ in the beginning or end (blog-duplicates hereafter) and only 1% of them differ in the middle. Thus, blog-duplicates have a long matched sequence in their central parts. Based on this important observation, we present a novel algorithm, Central Match, to identify blog-duplicates efficiently and accurately. When searching a document database for possible log-duplicates of a given document, Central Match runs50 times faster than MinHashing. In addition, Central Match identifies blog-duplicates more accurately than MinHashing. According to our experiments, when the precisions of Min-Hashing and Central Match are fixed to 0.9, their recalls are around 0.5 and 0.9, respectively, which means Central Match finds 80% more blog-duplicates than MinHashing.

In this paper, we propose a new paper ranking algorithm that gives a high rank to papers which is credited by other authoritative papers or published in premier conferences or journals. Also, the proposed algorithm solves a problem that recent papers are rated poorly due to few citations.

In this paper, we propose a new approach to measure sim-ilarities among academic papers based on their references. Our similarity measure uses both in-link and out-link by transforming in-link and out-link into undirected links.

This paper proposes a new trajectory clustering scheme for objects moving on road networks. A trajectory on road networks can be defined as a sequence of road segments a moving object has passed by. We first propose a similarity measurement scheme that judges the degree of similarity by considering the total length of matched road segments. Then, we propose a new clustering algorithm based on such similarity measurement criteria by modifying and adjusting the FastMap and hierarchical clustering schemes. To evaluate the performance of the proposed clustering scheme, we also develop a trajectory generator considering the fact that most objects tend to move from the starting point to the destination point along their shortest path. The performance result shows that our scheme has the accuracy of over 95%.

A blog network, composed of blogs and their relations, may exhibit two different propensities characterized by the purpose of use: an information-oriented propensity and a friendship-oriented propensity. Both propensities coexist in a blog network, and the degree of these propensities may play an important role in business and policy decisions of blog-related business. In this paper, we propose an automated method for determining the propensity values of a blog network. First, classification is used to judge the propensity values of the relation between two blogs. Then, by adding up the propensity values of all the relations in the network, one determines the propensity values of the whole network. Through extensive experiments using a large volume of real-world blog data, we demonstrate our method achieves a high level of accuracy in determining the propensity values of a relation. The results also suggest the applicability of our approach for determining the propensity values of a network.

In the blogosphere, there exist posts relevant to a particular subject and blogs that show interests in the subject. In this paper, we define a set of such posts and blogs as "blog community" and propose a method for extracting the blog community associated with a particular subject. The proposed method is based on the idea that the blogs who have performed actions to the posts of a particular subject are the ones that have interests in the subject, and that the posts which have received actions from such blogs are the ones that contain the subject. The proposed method selects a small number of seed posts that contain the subject. Then, it selects the blogs that perform actions to the seed posts over some threshold and the posts that have received actions over some threshold. By repeating these two steps, it gradually expands the blog community. The experimental results show that the proposed method exhibits a higher level of accuracy than the methods proposed in prior research.

Blogspace is a primary example of online social networks. In blogspace, there are a number of communities, each of which consists of members having dense relationships with one another. In this paper, we address formation and evolution of blog communities. We first make two claims: (1) a high level of contents similarity of blogs increases the likelihood of their belonging to the same community in a blog network; (2) A high level of contents similarity of communities increases the possibility of their being merged into a bigger community in the future. We verify these claims by analyzing a large volume of real-world blog data of 2 millions bloggers through extensive experiments. Our results provide new insights towards subsequent research on formation and evolution of communities in a blog network.

The nearest neighbor search is an important operation widely-used in multimedia databases. In higher dimensions, most of previous methods for nearest neighbor search become inefficient and require to compute nearest neighbor distances to a large fraction of points in the space. In this paper, we present a new approach for processing nearest neighbor search with the Euclidean metric, which searches over only a small subset of the original space. This approach effectively approximates clusters by encapsulating them into geometrically regular shapes and also computes better upper and lower bounds of the distances from the query point to the clusters. For showing the effectiveness of the proposed approach, we perform extensive experiments. The results reveal that the proposed approach significantly outperforms the X-tree as well as the sequential scan.

This paper discusses an index-based subsequence matching that supports time warping in large sequence databases. Time warping enables finding sequences with similar patterns even when they are of different lengths. In our earlier work, we suggested an efficient method for whole matching under time warping. This method constructs a multi-dimensional index on a set of feature vectors, which are invariant to time warping, from data sequences. For filtering at feature space, it also applies a lower-bound function, which consistently underestimates the time warping distance as well as satisfies the triangular inequality.In this paper, we incorporate the prefix-querying approach based on sliding windows into the earlier approach. For indexing, we extract a feature vector from every subsequence inside a sliding window and construct a multi-dimensional index using a feature vector as indexing attributes. For query processing, we perform a series of index searches using the feature vectors of qualifying query prefixes. Our approach provides effective and scalable subsequence matching even with a large volume of a database. We also prove that our approach does not incur false dismissal. To verify the superiority of our method, we perform extensive experiments. The results reveal that our method achieves significant speedup with real-world S&P 500 stock data and with very large synthetic data.

This paper proposes a new novel method for similarity search that supports time warping in large sequence databases. Time warping enables finding sequences with similar patterns even when they are of different lengths. Previous methods for processing similarity search that supports time warping fail to employ multi-dimensional indexes without false dismissal since the time warping distance does not satisfy the triangular inequality. Our primary goal is to innovate on search performance without permitting any false dismissal. To attain this goal, we devise a new distance function D/sub tw-lb/ that consistently underestimates the time warping distance and also satisfies the triangular inequality D/sub tw-lb/ uses a 4-tuple feature vector that is extracted from each sequence and is invariant to time warping. For efficient processing of similarity search, we employ a multi-dimensional index that uses the 4-tuple feature vector as indexing attributes and D/sub tw-lb/ as a distance function. The extensive experimental results reveal that our method achieves significant speedup up to 43 times with real-world S&P 500 stock data and up to 720 times with very large synthetic data.

In this paper, w epropose a subsequence matching algorithm that supports normalization transform in timeseries databases.Normalization transform enables nding sequences with similar uctuation patterns although they are not close to each other before the normalization transform.Application of the existing whole matching algorithm supporting normalization transform to the subsequence matching is feasible, but requires an index for ev ery possible length of the query sequence causing serious overhead on both storage space and update time.The proposed algorithm generates indexes only for a small number of dierent lengths of query sequences.F or subsequence matching it selects the most appropriate index among them.We can obtain better searc h performance by using more indexes.We c a l l o u r approach index interp olation.We formally pro ve t h a t the proposed algorithm does not cause false dismissal.F or performance evaluation, we h a ve conducted experiments using the indexes for only ve dierent lengths out of the lengths 256 512 of the query sequence.The results show that the proposed algorithm outperforms the sequential scan by up to 14.6 times on the average when the selectivity of the query is 10 ;5 .

Spatial join finds pairs of spatial objects having a specific spatial relationship in spatial database systems. A number of spatial join algorithms have recently been proposed in the literature. Most of them, however, perform the join in the original space. Joining in the original space has a drawback of dealing with sizes of objects and thus has difficulty in developing a formal algorithm that does not rely on heuristics. In this paper, we propose a spatial join algorithm based on the transformation technique. An object having a size in the two-dimensional original space is transformed into a point in the four-dimensional transform space, and the join is performed on these point objects. This can be easily extended to n-dimensional cases. We show the excellence of the proposed approach through analysis and extensive experiments. The results show that the proposed algorithm has a performance generally better than that of the R*-based algorithm proposed by Brinkhoff et al. This is a strong indicating that corner transformation preserves clustering among objects and that spatial operations can be performed better in the transform space than in the original space. This reverses the common belief that transformation will adversely affect clustering. We believe that our result will provide a new insight towards transformation-based spatial query processing.

Spatial join finds pairs of spatial objects having a specific spatial relationship in spatial database systems. Since spatial join is a fairly expensive operation, we need an efficient algorithm taking advantage of the characteristics of available spatial access methods. In this paper, we propose a spatial join algorithm using corner transformation and show its excellence through experiments. To the extent of authors' knowledge, the spatial join processing using corner transformation is new. In corner transformation, two regions in one file joined with two adjacent regions in the other file share a large common area. The proposed algorithm utilizes this property in order to reduce the number of disk accesses for spatial join. Experimental results show that the performance of the algorithm is generally better than that of the R*-tree based algorithm proposed by Brinkhoff et al. (1993. 1994). This is a strong indication that corner transformation is a promising category of spatial access methods and that spatial operations can be performed better in the transform space than in the original space. This reverses the common belief that transformation will adversely effect the clustering. We also briefly mention that the join algorithm based on corner transformation has a nice property of being amenable to parallel processing. We believe that our result will provide a new insight towards transformation-based processing of spatial operations.