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.

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%.

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

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 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.