In real-world graphs, we often encounter missing feature situations where a few or the majority of node features, e.g., sensitive information, are missed. In such scenarios, directly utilizing Graph Neural Networks (GNNs) would yield sub-optimal results in downstream tasks such as node classification. Despite the emergence of a few GNN-based methods attempting to mitigate its missing situation, when only a few features are available, they rather perform worse than traditional structure-based models. To this end, we propose a novel framework that further illuminates the potential of classical Label Propagation (Oldie), taking advantage of Feature Propagation, especially when only a partial feature is available. Now called by GOODIE, it takes a hybrid approach to obtain embeddings from the Label Propagation branch and Feature Propagation branch. To do so, we first design a GNN-based decoder that enables the Label Propagation branch to output hidden embeddings that align with those of the FP branch. Then, GOODIE automatically captures the significance of structure and feature information thanks to the newly designed Structure-Feature Attention. Followed by a novel Pseudo-Label contrastive learning that differentiates the contribution of each positive pair within pseudo-labels originating from the LP branch, GOODIE outputs the final prediction for the unlabeled nodes. Through extensive experiments, we demonstrate that our proposed model, GOODIE, outperforms the existing state-of-the-art methods not only when only a few features are available but also in abundantly available situations. Source code of GOODIE is available at: https://github.com/SukwonYun/GOODIE.

In modern recommender systems, especially in e-commerce, predicting multiple targets such as click-through rate (CTR) and post-view conversion rate (CTCVR) is common. Multi-task recommender systems are increasingly popular in both research and practice, as they leverage shared knowledge across diverse business scenarios to enhance performance. However, emerging real-world scenarios and data privacy concerns complicate the development of a unified multi-task recommendation model.

Class-incremental learning aims to learn new classes in an incremental fashion without forgetting the previously learned ones. Several research works have shown how additional data can be used by incremental models to help mitigate catastrophic forgetting. In this work, following the recent breakthrough in text-to-image generative models and their wide distribution, we propose the use of a pre-trained Diffusion Model model as a source of additional data for class-incremental learning. Compared to competitive methods that rely on external, often unlabeled, datasets of real images, our approach can generate synthetic samples that belong to the same classes as the previously encountered images. This allows us to use those additional data samples not only in the distillation loss but also for replay in supervised losses such as the classification loss. Experiments on the competitive benchmarks CIFAR100, ImageNet-Subset, and ImageNet demonstrate how this new approach can be used to further improve the performance of state-of-the-art methods for class-incremental learning on large scale datasets.

Exemplar-free class incremental learning is a highly challenging setting where replay memory is unavailable. Methods relying on frozen feature extractors have drawn attention recently in this setting due to their impressive performances and lower computational costs. However, those methods are highly dependent on the data used to train the feature extractor and may struggle when an insufficient amount of classes are available during the first incremental step. To overcome this limitation, we propose to use a pre-trained text-to-image diffusion model in order to generate synthetic images of future classes and use them to train the feature extractor. Experiments on the standard benchmarks CIFAR100 and ImageNet-Subset demonstrate that our proposed method can be used to improve state-of-the-art methods for exemplar-free class incremental learning, especially in the most difficult settings where the first incremental step only contains few classes. Moreover, we show that using synthetic samples of future classes achieves higher performance than using real data from different classes, paving the way for better and less costly pre-training methods for incremental learning.

Abstract Online live streaming platforms, such as YouTube Live and Twitch, have seen a surge in popularity in recent years. These platforms allow viewers to send real-time gifts to streamers, which can bring significant profits and fame. However, there has been little research on the donation system used on live streaming platforms. This paper aims to fill this gap by building a continuous-time dynamic graph to model the interactions among viewers based on real-time chat messages and predict the real-time donations on live streaming platforms. To achieve this, we propose a novel model called the Temporal Difference Graph Neural Network (TDGNN) that incorporates imbalanced learning strategies to identify potential donors during live streaming. Our model can predict the exact time when donations will appear. We conduct extensive experiments on three live streaming video datasets and demonstrate that our proposed model is more effective and robust than other baseline methods from other fields.

Abstract There has been an increasing interest in developing embedding methods for heterogeneous graph-structured data. The state-of-the-art approaches often adopt a bi-level aggregation scheme, where the first level aggregates information of neighbors belonging to the same type or group, and the second level employs the averaging or attention mechanism to aggregate the outputs of the first level. We find that bi-level aggregation may suffer from a down-weighting issue and overlook individual node information, especially when there is an imbalance in the number of different typed relations. We develop a new simple yet effective single-level aggregation scheme with infomax encoding, named HIME, for unsupervised heterogeneous graph embedding. Our single-level aggregation scheme performs relation-specific transformation to obtain homogeneous embeddings before aggregating information from multiple typed neighbors. Thus, it emphasizes each neighbor’s equal contribution and does not suffer from the down-weighting issue. Extensive experiments demonstrate that HIME consistently outperforms the state-of-the-art approaches in link prediction, node classification, and node clustering tasks.

Modern recommender systems are required to adapt to the change in user preferences and item popularity. Such a problem is known as the temporal dynamics problem, and it is one of the main challenges in recommender system modeling. Different from the popular recurrent modeling approach, we propose a new solution named LeapRec to the temporal dynamic problem by using trajectory-based meta-learning to model time dependencies. LeapRec characterizes temporal dynamics by two complement components named global time leap (GTL) and ordered time leap (OTL). By design, GTL learns long-term patterns by finding the shortest learning path across unordered temporal data. Cooperatively, OTL learns short-term patterns by considering the sequential nature of the temporal data. Our experimental results show that LeapRec consistently outperforms the state-of-the-art methods on several datasets and recommendation metrics. Furthermore, we provide an empirical study of the interaction between GTL and OTL, showing the effects of long- and short-term modeling.

The fundamental operation of Graph Neural Networks (GNNs) is the feature aggregation step performed over neighbors of the node based on the structure of the graph. In addition to its own features, the node gets additional combined features from its neighbors for each hop. These aggregated features help define the similarity or dissimilarity of the nodes with respect to the labels and are useful for tasks like node classification. However, in real-world data, features of neighbors at different hops may not correlate with the node's features. Thus, any indiscriminate feature aggregation by GNN might cause the addition of noisy features leading to degradation in model's performance. In this work, we show that selective aggregation leads to better performance than default aggregation on the node classification task. Furthermore, we propose Dual-Net GNN architecture with a classifier model and a selector model. The classifier model trains over a subset of input node features to predict node labels while the selector model learns to provide optimal input subset to the classifier for best performance. These two models are trained jointly to learn the best subset of features that give higher accuracy in node label predictions. With extensive experiments, we show that our proposed model outperforms the state-of-the-art GNN models with remarkable improvements up to 27.8%.

When incrementally trained on new classes, deep neural networks are subject to catastrophic forgetting which leads to an extreme deterioration of their performance on the old classes while learning the new ones. Using a small memory containing few samples from past classes has shown to be an effective method to mitigate catastrophic forgetting. However, due to the limited size of the replay memory, there is a large imbalance between the number of samples for the new and the old classes in the training dataset resulting in bias in the final model. To address this issue, we propose to use the Balanced Softmax Cross-Entropy and show that it can be seamlessly combined with state-of-the-art approaches for class-incremental learning in order to improve their accuracy while also potentially decreasing the computational cost of the training procedure. We further extend this approach to the more demanding class-incremental learning without memory setting and achieve competitive results with memory-based approaches. Experiments on the challenging ImageNet, ImageNet-Subset, and CIFAR100 benchmarks with various settings demonstrate the benefits of our approach.

Graph Convolutional Network (GCN) has experienced great success in graph analysis tasks. It works by smoothing the node features across the graph. The current GCN models overwhelmingly assume that the node feature information is complete. However, real-world graph data are often incomplete and containing missing features. Traditionally, people have to estimate and fill in the unknown features based on imputation techniques and then apply GCN. However, the process of feature filling and graph learning are separated, resulting in degraded and unstable performance. This problem becomes more serious when a large number of features are missing. We propose an approach that adapts GCN to graphs containing missing features. In contrast to traditional strategy, our approach integrates the processing of missing features and graph learning within the same neural network architecture. Our idea is to represent the missing data by Gaussian Mixture Model (GMM) and calculate the expected activation of neurons in the first hidden layer of GCN, while keeping the other layers of the network unchanged. This enables us to learn the GMM parameters and network weight parameters in an end-to-end manner. Notably, our approach does not increase the computational complexity of GCN and it is consistent with GCN when the features are complete. We demonstrate through extensive experiments that our approach significantly outperforms the imputation based methods in node classification and link prediction tasks. We show that the performance of our approach for the case with a low level of missing features is even superior to GCN for the case with complete features.

Graph neural networks (GNNs) have achieved superior performance and gained significant interest in various domains. However, most of the existing GNNs are considered for homogeneous graphs, whereas real-world systems are usually modeled as heterogeneous graphs or heterogeneous information networks (HINs). Designing a GNN to fully capture the rich semantic information of HINs is significantly challenging owing to the heterogeneity and incompatibility of relations in HINs. To address these issues while utilizing the power of GNNs, we propose a novel unsupervised embedding approach, named Projected Graph Relation-Feature Attention Network (PGRA). PGRA is based on three mechanisms: 1) specific-relation projection that projects the representation vector of each node to a relation-specific space, 2) aggregation with a relation-feature attention network that learns salient neighbors in the aggregation by considering the features of the nodes and compatibility between the connected and target relations, 3) an elegantly designed loss function that captures both the first- and second-order proximities between nodes. The results of extensive experiments on seven real-world datasets illustrate that PGRA outperforms the state-of-the-art methods by a large margin.

Graphs arise naturally in numerous situations, including social graphs, transportation graphs, web graphs, protein graphs, etc. One of the important problems in these settings is to identify which nodes are important in the graph and how they affect the graph structure as a whole. Betweenness centrality and closeness centrality are two commonly used node ranking measures to find out influential nodes in the graphs in terms of information spread and connectivity. Both of these are considered as shortest path based measures as the calculations require the assumption that the information flows between the nodes via the shortest paths. However, exact calculations of these centrality measures are computationally expensive and prohibitive, especially for large graphs. Although researchers have proposed approximation methods, they are either less efficient or suboptimal or both. We propose the first graph neural network (GNN) based model to approximate betweenness and closeness centrality. In GNN, each node aggregates features of the nodes in multihop neighborhood. We use this feature aggregation scheme to model paths and learn how many nodes are reachable to a specific node. We demonstrate that our approach significantly outperforms current techniques while taking less amount of time through extensive experiments on a series of synthetic and real-world datasets. A benefit of our approach is that the model is inductive, which means it can be trained on one set of graphs and evaluated on another set of graphs with varying structures. Thus, the model is useful for both static graphs and dynamic graphs. Source code is available at https://github.com/sunilkmaurya/GNN_Ranking

Short-term prediction of volcanic eruptions is one of the ultimate objectives of volcanology. At Sakurajima volcano, an active volcano in Japan, experts monitor the volcanic sensor data and analyze the prior signal to predict the eruptions. Even though experts derived some patterns, it is hard to make a good prediction due to handcrafted features. To address this issue, we propose to predict eruptions using machine learning. In this paper, we attempt to predict the eruptions hourly by adapting several machine learning methods including traditional and deep learning approaches. As recurrent neural network is well-known for extracting the time-sensitive features, we propose the model especially for volcanic eruption prediction named VepNet. The assumption is based on domain knowledge that some specific triggers are the main causes of future eruptions. To take this advantage, VepNet deploys an attention layer to locate and prioritize these triggers in decision making. The extensive experiments ever conducted using data from Sakurajima volcano showed the effectiveness of deep learning approach over the traditional approach. On top of that, VepNet showed its effectiveness on prediction with AUC-score up to 0.8665. Moreover, an attempt has been made to explain the mechanism of the eruptions by analyzing the attention layer of VepNet. Lastly, to support volcano expert in issuing warnings and the safety of living people around Sakurajima, a warning system named 3LWS is proposed. The system predicted the eruptions hourly with high accuracy and reliability with the eruption rate up to 68.97% in the High-Risk level.

In this work, we develop quantitative results to the learnability of a two-layers Graph Convolutional Network (GCN). Instead of analyzing GCN under some classes of functions, our approach provides a quantitative gap between a two-layers GCN and a two-layers MLP model. From the graph signal processing perspective, we provide useful insights to some flaws of graph neural networks for vertex classification. We empirically demonstrate a few cases when GCN and other state-of-the-art models cannot learn even when true vertex features are extremely low-dimensional. To demonstrate our theoretical findings and propose a solution to the aforementioned adversarial cases, we build a proof of concept graph neural network model with different filters named Graph Filters Neural Network (gfNN)1.

Variational Graph Autoencoders (VGAE) has recently been a popular framework of choice for learning representations on graphs. Its inception has allowed models to achieve state-of-the-art performances for challenging tasks such as link prediction, rating prediction and node clustering. However, a fundamental flaw exists in Variational Autoencoder (VAE) based approaches. Specifically, the objective function of VAE (reconstruction loss), deviates from its primary objective (i.e clustering). In this paper, we attempt to address this issue by introducing two significant changes to Variational Graph Autoencoder for Community Detection (VGAECD). Firstly, we introduce a simplified graph convolution encoder to increase convergence speed and reduce computational time. Secondly, a dual variational objective is introduced to encourage learning of the primary objective. The outcome is a faster converging model with competitive community detection performance.

Betweenness centrality is an important measure to find out influential nodes in networks in terms of information spread and connectivity. However, the exact calculation of betweenness centrality is computationally expensive. Although researchers have proposed approximation methods, they are either less efficient, or suboptimal, or both. In this paper, we present a Graph Neural Network(GNN) based inductive framework which uses constrained message passing of node features to approximate betweenness centrality. As far as we know, we are the first to propose a GNN based model to accomplish this task. We demonstrate that our approach dramatically outperforms current techniques while taking less amount of time through extensive experiments on a series of real-world datasets.

We propose a general view that demonstrates the relationship between network embedding approaches and matrix factorization. Unlike previous works that present the equivalence for the approaches from a skip-gram model perspective, we provide a more fundamental connection from an optimization (objective function) perspective. We demonstrate that matrix factorization is equivalent to optimizing two objectives: one is for bringing together the embeddings of similar nodes; the other is for separating the embeddings of distant nodes. The matrix to be factorized has a general form: S-β. The elements of $\mathbfS $ indicate pairwise node similarities. They can be based on any user-defined similarity/distance measure or learned from random walks on networks. The shift number β is related to a parameter that balances the two objectives. More importantly, the resulting embeddings are sensitive to β and we can improve the embeddings by tuning β. Experiments show that matrix factorization based on a new proposed similarity measure and β-tuning strategy significantly outperforms existing matrix factorization approaches on a range of benchmark networks.

Advancements in deep neural networks have revolutionized the way how we conduct our day-to-day activities ranging from how we unlock our phones to self-driving cars. Convolutional Neural Networks (CNN) play the principal role in learning high level feature representations from visual inputs. It is crucial to know how reliable those neural networks are as human lives can be at stake. Recent experiments on the robustness of CNNs show that they are highly susceptible to small adversarial perturbations. Due to the increasing popularity of mobile devices, there is a significant demand for CNN models which are smaller enough to run on a mobile device without sacrificing the accuracy. Although recent researches have been successful at achieving smaller models with comparable accuracy on standard image datasets, their robustness to adversarial attacks has not been studied. However, massive deployment of smaller models on millions of mobile devices stresses importance of their robustness. In this work, we study how robust such models are with respect to state-of-the-art compression techniques such as quantization. Our contributions are summarized as follows: (1) insights to achieve smaller and robust models (2) a compression framework which is adversarial-aware. Our findings reveal that compressed models are naturally more robust than compact models. This provides an incentive to perform compression rather than designing compact models. Additionally, the latter provides benefits of increased accuracy and higher compression rate, up to 90×.

Discovering community structure in networks remains a fundamentally challenging task. From scientific domains such as biology, chemistry and physics to social networks the challenge of identifying community structures in different kinds of network is challenging since there is no universal definition of community structure. Furthermore, with the surge of social networks, content information has played a pivotal role in defining community structure, demanding techniques beyond its traditional approach. Recently, network representation learning have shown tremendous promise. Leveraging on recent advances in deep learning, one can exploit deep learning's superiority to a network problem. Most predominantly, successes in supervised and semi-supervised task has shown promising results in network representation learning tasks such as link prediction and graph classification. However, much has yet to be explored in the literature of community detection which is an unsupervised learning task. This paper proposes a deep generative model for community detection and network generation. Empowered with Bayesian deep learning, deep generative models are capable of exploiting non-linearities while giving insights in terms of uncertainty. Hence, this paper proposes Variational Graph Autoencoder for Community Detection (VGAECD). Extensive experiment shows that it is capable of outperforming existing state-of-the-art methods. The generalization of the proposed model also allows the model to be considered as a graph generator. Additionally, unlike traditional methods, the proposed model does not require a predefined community structure definition. Instead, it assumes the existence of latent similarity between nodes and allows the model to find these similarities through an automatic model selection process. Optionally, it is capable of exploiting feature-rich information of a network such as node content, further increasing its performance.

Graph protection strategies aim to suppress the epidemic propagation in a network by allocating protection resources to maximize the ratio of surviving node. Research on this topic has been active and promising due to its wide-range applications. However, most of the recent developments are simulated by assuming that the network structure remains static during epidemics. Moreover, the existing protection schemes are limited to the simplified pre-emptive and post-emptive schemes. The pre-emptive scheme protects the most critical nodes of networks prior to epidemic spreading, behaving as a prevention mechanism. In post-emptive schemes, the protections are allocated in the presence of epidemics, when the attacks have already spread over the network, simulating a late curative response. Given a limited k resource budget, both of those schemes spend the whole resources in a single chance. In this paper, we introduce a novel adaptive protection scheme by gradually protecting nodes in response to the incoming attacks. We consider the adaptive scheme in a more challenging network structure, the dynamic networks. We propose the n-step fitted Q-learning for training the model under reinforcement approach. We further incorporate graph embedding as a feature-based representation of the network state. We also demonstrate the potential of our proposal as a non-deterministic approach for this graph protection problem. Experimental results show that our proposed model effectively restrain epidemic propagation in real-world network datasets.

Given a large graph, such as social network, how to determine set of vertices should we protect given the k budget such that the percentage of vertices that remain uninfected at the end of infection propagation is maximized? Considering the intricacy of this problem and the requirement of scalability, the existing methods are not scalable. On the other hand, the connections among vertices in many real world contagions are usually not solely binary entities (either present or not) but have associated magnitudes and directions. We formulate the flow-aware vertex protection (FAVP) problem to elaborate more efficient and realistic way to prevent infection spreading in graphs by protecting a set of vertices. We also demonstrate that the FAVP problem is NP-Hard. Finally, we propose an efficient and scalable algorithm, called GraphShield by taking into account the role of infection flow, graph connectivity, and outdegree centrality. Experimental results on many real network datasets show that the GraphShield outperforms the state-of-the-art algorithms regarding both effectiveness and efficiency.

This paper proposes a novel method for transductive classification on heterogeneous information networks composed of multiple types of vertices. Such networks naturally represent many real-world Web data such as DBLP data (author, paper, and conference). Given a network where some vertices are labeled, the classifier aims to predict labels for the remaining vertices by propagating the labels to the entire network. In the label propagation process, many studies reduce the importance of edges connecting to a high-degree vertex. The assumption is unsatisfactory when reliability of a label of a vertex cannot be implied from its degree. On the basis of our intuition that edges bridging across communities are less trustworthy, we adapt edge betweenness to imply the importance of edges. Since directly applying the conventional edge betweenness is inefficient on heterogeneous networks, we propose two additional refinements. First, the centrality utilizes the fact that networks contain multiple types of vertices. Second, the centrality ignores flows originating from endpoints of considering edges. The experimental results on real-world datasets show our proposed method is more effective than a state-of-the-art method, GNetMine. On average, our method yields 92.79 ± 1.25% accuracy on a DBLP network even if only 1.92% of vertices are labeled. Our simple weighting scheme results in more than 5 percentage points increase in accuracy compared with GNetMine.

Modularity is a widely used measure for evaluating community structure in networks. The definition of modularity involves a comparison between the observed network and a null model, which serves as a reference. To make the comparison significant, this null model should characterize some features of the observed network. However, the previously used null models are not good representations of real-world networks. A common feature of many real-world networks is similarity attraction, i.e., nodes that are similar have a higher chance of getting connected. We propose a new null model that captures this feature. Based on our null model, we create a unified measure Dist-Modularity, which incorporates the famous Newman-Girvan modularity as a special case. We use three examples to demonstrate that Dist-Modularity is useful in detecting 1) the multi-resolution communities and 2) the geographically dispersed communities.

Online social media such as delicious and digg are represented as tripartite networks whose vertices are users, tags, and resources. Detecting communities from such tripartite networks is practically important. Modularity is often used as the criteria for evaluating the goodness of network divisions into communities. For tripartite networks, Neubauer defines a tripartite modularity which extends Murata's bipartite modularity. However, Neubauer's tripartite modularity still uses projections and it will lose information that original tripartite networks have. This paper proposes new tripartite modularity for tripartite networks that do not use projections. Experimental results show that better community structures can be detected by optimizing our tripartite modularity.

Community detection in networks receives much attention recently. Most of the previous works are for unipartite networks composed of only one type of nodes. In real world situations, however, there are many bipartite networks composed of two types of nodes. In this paper, we propose a fast algorithm called LP&BRIM for community detection in large-scale bipartite networks. It is based on a joint strategy of two developed algorithms -- label propagation (LP), a very fast community detection algorithm, and BRIM, an algorithm for generating better community structure by recursively inducing divisions between the two types of nodes in bipartite networks. Through experiments, we demonstrate that this new algorithm successfully finds meaningful community structures in large-scale bipartite networks in reasonable time limit.

Question-Answering Bulletin Boards (QABB), such as Yahoo! Answers and Windows Live QnA, are gaining popularity recently. Communications on QABB connect users, and the overall connections can be regarded as a social network. If the evolution of social networks can be predicted, it is quite useful for encouraging communications among users. This paper describes an improved method for predicting links based on weighted proximity measures of social networks. The method is based on an assumption that proximities between nodes can be estimated better by using both graph proximity measures and the weights of existing links in a social network. In order to show the effectiveness of our method, the data of Yahoo! Chiebukuro (Japanese Yahoo! Answers) are used for our experiments. The results show that our method outperforms previous approaches, especially when target social networks are sufficiently dense.

Analyzing users' Web log data and extracting their interests of Web-watching behaviors are important and challenging research topics of Web usage mining. Users visit their favorite sites and sometimes search new sites by performing keyword search on search engines. Users' Web-watching behaviors can be regarded as a graph since visited Web sites and entered search keywords are connected with each other in a time sequence. We call this graph as a site-keyword graph. This paper describes a method for clarifying users' interests based on an analysis of the site-keyword graph. The method is for extracting subgraphs representing users' routine visit from a site-keyword graph which is generated from augmented Web audience measurement data (Web log data). Experimental result shows that our new method succeeds in finding subgraphs which contain most of users' interested sites

Analyzing users' Web log data and extracting their interests of Web-watching behaviors are important and challenging research topics of Web usage mining. Users visit their favorite sites and sometimes search new sites by performing keyword search on search engines. Users' Web-watching behaviors can be regarded as a graph since visited Web sites and entered search keywords are connected with each other in a time sequence. We call this graph a site-keyword graph. This paper describes a method for clarifying users' interests based on an analysis of the site-keyword graph. The method is for extracting subgraphs representing users' main interests from a site-keyword graph which is generated from augmented Web audience measurement data (Web log data). Experimental results show that our new method succeeds in finding subgraphs which contain most of the sites that users are interested in

As the research of Web structure mining, several attempts have been made for discovering group of related Web pages (Web communities) such as Kumar's trawling and Flake's method. There are groups of users who watch such related Web pages, and discovering such groups (user communities) is important for clarifying the behaviors of the users of similar tastes. Moreover, it is expected that the characteristics of user communities in the Web correspond to that in real human societies. A method for discovering user communities is described in this paper. Client-level log data (Web audience measurement data) is used as the data of users' Web watching behaviors. Maximal complete bipartite graphs are searched from the graph obtained from the log data without analyzing the contents of Web pages. Experimental results show that our method succeeds in discovering many interesting user communities with labels that characterize the communities.