Vision models fail both under tiny pixel attacks and under real-world shifts in style or background because they latch onto spurious features. We propose a two-step, label-free method. (1) Spurious-Invariant Self-Supervised Pre-training (SISSP) trains an encoder to collapse representations of the same object despite randomized styles and backgrounds, pruning shortcut signals. (2) Semantic-Alignment Adversarial Refinement (SAAR) takes any attack and projects it back into a small ball within SISSP feature space, yielding adversaries that look natural yet still fool the classifier. Fine-tuning with SISSP features and SAAR images produces a ResNet-50 that retains 64% ImageNet accuracy, 46% PGD robustness without environment labels or specialized augmentations. Together, SISSP provides a semantics-aware metric and SAAR generates on-manifold adversaries, achieving the first ImageNet-scale model robust to both pixel-level noise and semantic shifts.

Temporal Graph Neural Networks (TGNNs) have emerged as powerful tools for modeling dynamic interactions across various domains. The design space of TGNNs is notably complex, given the unique challenges in runtime efficiency and scalability raised by the evolving nature of temporal graphs. We contend that many of the existing works on TGNN modeling inadequately explore the design space, leading to suboptimal designs. Viewing TGNN models through a performance-focused lens often obstructs a deeper understanding of the advantages and disadvantages of each technique. Specifically, benchmarking efforts inherently evaluate models in their original designs and implementations, resulting in unclear accuracy comparisons and misleading runtime. To address these shortcomings, we propose a practical comparative evaluation framework that performs a design space search across well-known TGNN modules based on a unified, optimized code implementation. Using our framework, we make the first efforts towards addressing three critical questions in TGNN design, spending over 10,000 GPU hours: (1) investigating the efficiency of TGNN module designs, (2) analyzing how the effectiveness of these modules correlates with dataset patterns, and (3) exploring the interplay between multiple modules. Key outcomes of this directed investigative approach include demonstrating that the most recent neighbor sampling and attention aggregator outperform uniform neighbor sampling and MLP-Mixer aggregator; Assessing static node memory as an effective node memory alternative, and showing that the choice between static or dynamic node memory should be based on the repetition patterns in the dataset. Our in-depth analysis of the interplay between TGNN modules and dataset patterns should provide a deeper insight into TGNN performance along with potential research directions for designing more general and effective TGNNs.

Graph neural networks (GNNs) have gained significant attention across diverse areas due to their superior performance in learning graph representations. While GNNs exhibit superior performance compared to other methods, they are primarily designed for homogeneous graphs, where all nodes and edges are of the same type. Training a GNN model for large-scale graphs incurs high computation and storage costs, especially when considering the heterogeneous structural information of each node. To address the demand for efficient GNN training, various sampling methods have been proposed. In this paper, we propose a sampling method based on bandit sampling, an online learning algorithm with provable convergence under weak assumptions on the learning objective. To the best of our knowledge, this is the first bandit-based sampling method applied to heterogeneous GNNs with a theoretical guarantee. The main idea is to prioritize node types with more informative connections with respect to the learning objective. Compared with existing techniques for GNN training on heterogeneous graphs, extensive experiments using the Open Academic Graph (OAG) dataset demonstrate that our proposed method outperforms the state-of-the-art in terms of the runtime across various tasks with a speed-up of 1.5-2x, while achieving similar accuracy.

Multi-Agent Reinforcement Learning (MARL) has achieved significant success in large-scale AI systems and big-data applications such as smart grids, surveillance, etc. Existing advancements in MARL algorithms focus on improving the rewards obtained by introducing various mechanisms for inter-agent cooperation. However, these optimizations are usually compute- and memory-intensive, thus leading to suboptimal speed performance in end-to-end training time. In this work, we analyze the speed performance (i.e., latency-bounded throughput) as the key metric in MARL implementations. Specifically, we first introduce a taxonomy of MARL algorithms from an acceleration perspective categorized by (1) training scheme and (2) communication method. Using our taxonomy, we identify three state-of-the-art MARL algorithms - Multi-Agent Deep Deterministic Policy Gradient (MADDPG), Target-oriented Multi-agent Communication and Cooperation (ToM2C), and Networked Multi-Agent RL (NeurComm) - as target benchmark algorithms, and provide a systematic analysis of their performance bottlenecks on a homogeneous multi-core CPU platform. We justify the need for MARL latency-bounded throughput to be a key performance metric in future literature while also addressing opportunities for parallelization and acceleration.

Temporal Knowledge Graphs store events in the form of subjects, relations, objects, and timestamps which are often represented by dynamic heterogeneous graphs. Event forecasting is a critical and challenging task in Temporal Knowledge Graph reasoning that predicts the subject or object of an event in the future. To obtain temporal embeddings multi-step away in the future, existing methods learn generative models that capture the joint distribution of the observed events. To reduce the high computation costs, these methods rely on unrealistic assumptions of independence and approximations in training and inference. In this work, we propose SeDyT, a discriminative framework that performs sequence modeling on the dynamic entity embeddings to solve the multi-step event forecasting problem. SeDyT consists of two components: a Temporal Graph Neural Network that generates dynamic entity embeddings in the past and a sequence model that predicts the entity embeddings in the future. Compared with the generative models, SeDyT does not rely on any heuristic-based probability model and has low computation complexity in both training and inference. SeDyT is compatible with most Temporal Graph Neural Networks and sequence models. We also design an efficient training method that trains the two components in one gradient descent propagation. We evaluate the performance of SeDyT on five popular datasets. By combining temporal Graph Neural Network models and sequence models, SeDyT achieves an average of 2.4% MRR improvement when not using the validation set and more than 10% MRR improvement when using the validation set.

Graph Neural Networks (GNNs) are proven to be powerful models to generate node embedding for downstream applications. However, due to the high computation complexity of GNN inference, it is hard to deploy GNNs for large-scale or real-time applications. In this paper, we propose to accelerate GNN inference by pruning the dimensions in each layer with negligible accuracy loss. Our pruning framework uses a novel LASSO regression formulation for GNNs to identify feature dimensions (channels) that have high influence on the output activation. We identify two inference scenarios and design pruning schemes based on their computation and memory usage for each. To further reduce the inference complexity, we effectively store and reuse hidden features of visited nodes, which significantly reduces the number of supporting nodes needed to compute the target embedding. We evaluate the proposed method with the node classification problem on five popular datasets and a real-time spam detection application. We demonstrate that the pruned GNN models greatly reduce computation and memory usage with little accuracy loss. For full inference, the proposed method achieves an average of 3.27X speedup with only 0.002 drop in F1-Micro on GPU. For batched inference, the proposed method achieves an average of 6.67X speedup with only 0.003 drop in F1-Micro on CPU. To the best of our knowledge, we are the first to accelerate large scale real-time GNN inference through channel pruning.

Tip decomposition is a crucial kernel for mining dense subgraphs in bipartite networks, with applications in spam detection, analysis of affiliation networks etc. It creates a hierarchy of vertex-induced subgraphs with varying densities determined by the participation of vertices in butterflies (2, 2-bicliques). To build the hierarchy, existing algorithms iteratively follow a delete-update (peeling) process: deleting vertices with the minimum number of butterflies and correspondingly updating the butterfly count of their 2-hop neighbors. The need to explore 2-hop neighborhood renders tip-decomposition computationally very expensive. Furthermore, the inherent sequentiality in peeling only minimum butterfly vertices makes derived parallel algorithms prone to heavy synchronization. In this paper, we propose a novel parallel tip-decomposition algorithm - REfine CoarsE-grained Independent Tasks (RECEIPT) that relaxes the peeling order restrictions by partitioning the vertices into multiple independent subsets that can be concurrently peeled. This enables RECEIPT to simultaneously achieve a high degree of parallelism and dramatic reduction in synchronizations. Further, RECEIPT employs a hybrid peeling strategy along with other optimizations that drastically reduce the amount of wedge exploration and execution time. We perform detailed experimental evaluation of RECEIPT on a shared-memory multicore server. It can process some of the largest publicly available bipartite datasets orders of magnitude faster than the state-of-the-art algorithms - achieving up to 1100× and 64× reduction in the number of thread synchronizations and traversed wedges, respectively. Using 36 threads, RECEIPT can provide up to 17.1× self-relative speedup.

To improve the reliability of content shared on social media, effective strategies for mitigating the diffusion of fake news are increasingly necessary. Traditionally, to counter false belief a competing cascade approach is used. This approach assumes that the opposite belief is already known, and thus, not applicable to newly spreading fake news. Another approach is to block nodes and links of the network to impede the flow of fake news (rumor/influence blocking). However, a more active way to battle the dissemination of fake news is to propagate the corresponding real news, since people who receive the real news in tandem with the fake news are less likely to believe in fake news. Such a setting is especially useful on a messaging platform such as WhatsApp, where the news item flows as a private message and the correction of fake news and its propagation must be performed by the users within the network as they receive it. To achieve this goal, we propose network-based recruitment for active fake news correction (RecANt) to find a set of individuals of a pre-defined size to be incentivized for actively fact-checking and passing on the real news so as to reach the maximum number of nodes in the network. These individuals should be such that they are likely to receive the fake news so that they can test its credibility, and when they propagate the corresponding real news, it reaches a large number of individuals. We prove that RecANt is NP-Hard with a monotone and submodular objective, leading to a polynomial time greedy algorithm (AFC) which provides a (1 - 1/e - ε)-approximation. We further optimize the runtime of AFC by developing a fast graph-pruning heuristic (RAFC) that performs as well as AFC in checking the spread of fake news while reducing the runtime significantly. Simulations on several networks demonstrate that our approach outperforms popular social network centrality measures and state-of-the-art information diffusion algorithm.

Accurate prediction of crime incidents can assist the police in better planning of prevention strategies and scheduling deployment. The problem is often studied as a spatio-temporal regression problem approached by dividing the area of interest into a grid of uniform cells, and performing regression on timeseries of each cell. We propose that changing the method of division of the area can significantly improve crime prediction. We demonstrate this using a heterogeneous division of the area obtained by our partitioning algorithm that takes into account the density of crime. We further show that existing measures do not provide a fair comparison of two methods that partition the area in two different ways. To address this severe drawback in crime prediction evaluation, we propose a novel measure which is based on optimal allocation of resources relying on the prediction and then checking the actual number of crimes that would have been avoided by the allocation. Essentially, our measure answers the question of which model would have assisted in preventing most number of actual crimes if allocation were to be done using the predicted crimes. We also prove that a greedy algorithm results in the optimal allocation resources, thus making our evaluation computationally lightweight. Experiments on real-world datasets demonstrate that heterogeneous division of the area results in improved crime prediction while drastically decreasing the number of models to be trained compared to uniform grid division.

Hub labeling is widely used to improve the latency and throughput of Point-to-Point Shortest Distance (PPSD) queries in graph databases. However, constructing hub labeling, even via the state-of-the-art Pruned Landmark Labeling (PLL) algorithm is computationally intensive. PLL further has a sequential root order label dependency that makes it challenging to parallelize. Hence, the existing parallel approaches are often plagued by label size increase, poor scalability and inability to process large weighted graphs. In this paper, we develop novel algorithms that construct the minimal (guaranteed) Canonical Hub Labeling on shared and distributed-memory parallel systems in a scalable and efficient manner. Our key contribution, the PLaNT algorithm, provides an embarrassingly parallel approach for label construction that scales well beyond the limits of current practice. Our approach is the first to employ a collaborative label partitioning scheme across multiple nodes of a cluster, for completely in-memory labeling and parallel querying on massive graphs whose labels cannot fit on a single node. On a single node with 72-threads, our shared-memory algorithm is up to 47.4X faster than sequential PLL. While our labeling time is comparable to the state-of-the-art shared-memory paraPLL, our label size is 17% smaller on average. PLaNT demonstrates superior parallel scalability. It can process significantly larger graphs and construct labeling orders of magnitude faster than the state-of-the-art distributed paraPLL. Compared to the best shared-memory parallel algorithm, it achieves up to 9.5X speedup on a 64 node cluster.

Interventions to reduce violence among homeless youth are difficult to implement due to the complex nature of violence. However, a peer-based intervention approach would likely be a worthy approach as it has been shown that individuals who interact with more violent individuals are more likely to be violent, suggesting a contagious nature of violence. We propose Uncertain Voter Model to represent the complex process of diffusion of violence over a social network, that captures uncertainties in links and time over which the diffusion of violence takes place. Assuming this model, we define Violence Minimization problem where the task is to select a predefined number of individuals for intervention so that the expected number of violent individuals in the network is minimized over a given time-frame. We extend the problem to a probabilistic setting, where the success probability of converting an individual into non-violent is a function of the number of “units” of intervention performed on them. We provide algorithms for finding the optimal intervention strategies for both scenarios. We demonstrate that our algorithms perform significantly better than interventions based on popular centrality measures in terms of reducing violence.

Subgraph isomorphism is a fundamental graph problem with many applications. Due to its NP-Hard nature, subgraph isomorphism in large dynamic graphs is considered as a challenging problem. In this paper, we present a distributed graph pruning algorithm (D-IDS) for dynamic graphs to enable efficient subgraph isomorphism. D-IDS continuously maintains the maximum dual simulation match in a dynamic graph. We develop D-ISI, a distributed incremental algorithm for subgraph isomorphism that utilizes D-IDS. We evaluated our algorithms on a commodity cluster in Amazon EC2 using real world graph datasets. Our evaluation results show that the graph pruning technique is highly effective on graphs with small diameter where it achieves over 60% reduction in graph size.