The 3D Variable Scene Graph (3DVSG) is a newly emerging representation for modeling dynamic environments, extending scene graphs by introducing a node-level property called variability, which quantifies the likelihood of semantic change over time. In this work, we explore the integration of pre-trained language models (PLMs) into variability estimation. This is of significant practical importance because variability estimation suffers from data scarcity and severe class imbalance. PLMs provide a rich general semantic knowledge that can enhance representation learning in such settings. We systematically evaluate PLM embeddings across different graph neural networks (GNNs). We introduce a template-based text structuring (TTS) to understand the effect of input formatting. Our experiments show that PLM embeddings significantly improve variability estimation performance, with effectiveness influenced by both embedding and GNN choices. Also, we demonstrate that text structure can significantly affect embedding quality. Lastly, we demonstrate that PLM embeddings yield reliable gains in variability estimation and downstream active change detection.

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.

Abstract Commonsense explanation generation refers to reasoning and explaining why a commonsense statement contradicts commonsense knowledge, such as why the statement “My dad grew volleyballs in his garden” is nonsensical. While such reasoning is trivial for humans, it remains a challenge for AI systems. Despite their notable performance in tasks like text generation and reasoning, large language models (LLMs) often fall short of consistently generating coherent and accurate commonsense explanations. To bridge this gap, we propose a novel Two-stage Identification and Prompting (TIP) framework for enhancing LLMs’ ability to handle the task of commonsense explanation generation. Specifically, in the first stage, TIP identifies the nonsensical concept in the given statement, pinpointing the specific element that contradicts commonsense knowledge. In the second stage, TIP generates implicit knowledge based on the identified nonsensical concept and then leverages this implicit knowledge to guide the adopted LLMs in generating explanations. In order to demonstrate the effectiveness of the proposed TIP framework for commonsense explanation generation, we conducted extensive experiments based on the ComVE dataset and a newly constructed CSE dataset, where a variety of LLMs are evaluated. The experimental results show that TIP consistently outperforms all baseline methods across multiple metrics, demonstrating its effectiveness in improving LLMs’ commonsense reasoning and explanation generation capabilities.

Modern recommender systems heavily rely on high-quality representations learned from high-dimensional sparse data. While significant efforts have been invested in designing powerful algorithms for extracting user preferences, the factors contributing to good representations have remained relatively unexplored. In this work, we shed light on an issue in the existing pairwise learning paradigm (i.e., embedding collapse), that the representations tend to span a subspace of the whole embedding space, leading to a suboptimal solution and reducing the model capacity. Specifically, we show that alignment of positive pairs is equivalent to a low-pass filter causing users and items to collapse to a constant vector. While negative sampling can partially mitigate this issue by acting as a high-pass filter to balance the spectrum, leading to an incomplete collapse. To tackle this issue, we present a novel learning paradigm DirectSpec, which directly optimizes the spectrum distribution to ensure that users and items effectively span the entire embedding space. We demonstrate that many self-supervised learning algorithms without explicit negative sampling can be considered as special cases of DirectSpec. Furthermore, we show that optimizing the spectrum inappropriately could also be detrimental to data representation, where the key lies in a dynamic balance between alignment of positive pairs and spectrum balancing. Finally, we propose an enhanced and practical implementation DirectSpec + to balance the embedding spectrum more adaptively and effectively. We implement DirectSpec + on two popular recommender models: matrix factorization and LightGCN. Our experimental results demonstrate its effectiveness and efficiency over competitive baselines.

It has been shown that the effectiveness of graph convolutional network (GCN) for recommendation is attributed to the spectral graph filtering. Most GCN-based methods consist of a graph filter or followed by a low-rank mapping optimized based on supervised training. However, we show two limitations suppressing the power of graph filtering: (1) Lack of generality. Due to the varied noise distribution, graph filters fail to denoise sparse data where noise is scattered across all frequencies, while supervised training results in worse performance on dense data where noise is concentrated in middle frequencies that can be removed by graph filters without training. (2) Lack of expressive power. We theoretically show that linear GCN (LGCN) that is effective on collaborative filtering (CF) cannot generate arbitrary embeddings, implying the possibility that optimal data representation might be unreachable.

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

Forecasting incident occurrences (e.g. crime, EMS, traffic accident) is a crucial task for emergency service providers and transportation agencies in performing response time optimization and dynamic fleet management. However, such events are by nature rare and sparse, which causes the label imbalance problem and inferior performance of models relying on data sufficiency. The existing studies circumvent, instead of truly solving, this issue by defining the incident prediction problem in a coarse-grained temporal (e.g. daily) setting, which leaves the proposed models unrobust to fine-grained dynamics and trivial for the real-world decision making. In this paper, we tackle the temporally fine-grained incident prediction problem in a sparse setting by explicitly exploiting the behind-the-scene chainlike triggering mechanism. Moreover, this chain effect roots in multiple domains (i.e. spatial, categorical), which further entangles with the temporal dimension and happens to be time-variant. To be specific, we propose a novel deep learning framework, namely Spatio-Temporal-Categorical Graph Neural Networks (STC-GNN), to handle the multidimensional and dynamic chain effect for performing fine-grained multi-incident co-prediction. Extensive experiments on three real-world city-level incident datasets verify the insightfulness of our perspective and effectiveness of the proposed model.

Forecasting regional ambulance demand plays a fundamental part in dynamic fleet allocation and redeployment. This topic has been gaining increasing significance, as virtually every country is experiencing an aging population, with generally higher level of vulnerability and demand for the emergency medical service (EMS). Although exploring the spatial and temporal correlations in EMS historical records, the existing methods principally consider the former time-invariant, which does not necessarily hold in reality. Moreover, this assumption ignores the fact that the behind-the-scenes dynamics are people, whose demographic profiles and activity patterns could be determinants of regional EMS demands. In this paper, we are therefore motivated to mine the collective daily routines in human mobility, to further represent the evolving spatial correlations. Particularly, we model profiled mobility groups as multiple random walkers and propose a novel bicomponent neural network, including a heterogeneous multi-graph convolution layer and spatio-temporal interlacing attention module, to perform the prediction task. Experimental results on the real-world data verify the effectiveness of introducing dynamic human mobility and the advantage of our approach over the state-of-the-art models.

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

Acknowledging the dynamic nature of knowledge graphs, the problem of learning temporal knowledge graph embeddings has recently gained attention. Essentially, the goal is to learn vector representation for the nodes and edges of a knowledge graph taking time into account. These representations must preserve certain properties of the original graph, so as to allow not only classification or clustering tasks, as for classical graph embeddings, but also approximate time-dependent query answering or link predictions over knowledge graphs. For instance, "who was the leader of Germany in 1994?'' or "when was Bonn the capital of Germany?''

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.

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.

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.

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.