This work focuses on enhancing autonomous vehicle navigation systems by leveraging the semantic information contained in traffic signs, with a particular emphasis on text-based signs. We introduce an approach to interpret the text on signs for downstream autonomous vehicle applications, such as determining parking restrictions and identifying roadwork zones and directional commands. Specifically, we build upon our previously developed method [1] to create a more fine-grained representation of traffic sign parsing and utilize a pre-trained language model in a constrained setting. This approach helps alleviate the need for hand-crafted rules, making our method significantly more scalable. Our approach decomposes the parsing task into simpler tasks, each of which can be implemented using a single lightweight transformer-based language model, thereby improving efficiency and interpretability. We demonstrate the effectiveness of our method through experiments, showing substantial improvements in accuracy over a previously introduced baseline. To the best of our knowledge, this is the first application of a unified language model to this task, representing a significant step toward open-world sign interpretation.

Graphs are powerful analytic tools for modeling adversarial activities across a wide range of domains and applications. Examples include identifying and responding to cybersecurity systems' threats and vulnerabilities, strengthening critical infrastructure's resilience and robustness, and combating covert illicit activities that span various domains like finance, communication, and transportation. With the rapid development of generative AI, the lifecycle and throughput of adversarial activities, such as generating attacks or synthesizing deceptive signals, have accelerated significantly. For instance, a malicious actor can generate a large number of malware variants to flood defense systems or create agents to disseminate misleading signals, obscuring their activities. Consequently, there is a pressing need for novel and effective technology to autonomously handle these adversarial activities and keep pace with the evolving threats. The purpose of this workshop is to provide a forum to discuss emerging research problems and novel approaches in graph analysis for modeling adversarial activities in the age of generative AI.

There have been tremendous efforts over the past decades dedicated to the generation of realistic graphs in a variety of domains, ranging from social networks to computer networks, from gene regulatory networks to online transaction networks. Despite the remarkable success, the vast majority of these works are unsupervised in nature and are typically trained to minimize the expected graph reconstruction loss, which would result in the representation disparity issue in the generated graphs, i.e., the protected groups (often minorities) contribute less to the objective and thus suffer from systematically higher errors. In this paper, we aim to tailor graph generation to downstream mining tasks by leveraging label information and user-preferred parity constraints. In particular, we start from the investigation of representation disparity in the context of graph generative models. To mitigate the disparity, we propose a fairness-aware graph generative model named Fairgen. Our model jointly trains a label-informed graph generation module and a fair representation learning module by progressively learning the behaviors of the protected and unprotected groups, from the ‘easy’ concepts to the ‘hard’ ones. In addition, we propose a generic context sampling strategy for graph generative models, which is proven to be capable of fairly capturing the contextual information of each group with a high probability. Experimental results on seven real-world data sets demonstrate that Fairgen (1) obtains performance on par with state-of-the-art graph generative models across nine network properties, (2) mitigates the representation disparity issues in the generated graphs, and (3) substantially boosts the model performance by up to 17% in downstream tasks via data augmentation.

Malware poses an ever-growing threat to organizations, governments, and institutions. To effectively combat its proliferation and development by threat actors, identifying the authors of malware is a crucial step. Existing efforts in malware authorship attribution often focus on extracting stylistic features from source code. However, malware source code is frequently limited in availability. There is a strong need to develop effective methods to directly extract a robust and salient representation from malware binaries. This representation should adeptly capture the inherent characteristics of the binaries to facilitate the identification of malware authors. In our work, we introduce an approach that leverages multi-view graph representation learning for malware authorship attribution. We extract various intermediate representations from the binary, including control flow graphs and function call graphs. These representations are encoded using GNN-based functions and fused to create a comprehensive malware representation. Additionally, we introduce GNN-explainability approaches to identify subgraphs indicative of class membership. Our experiments on a recent benchmark demonstrate significant performance enhancements in authorship attribution.

Autonomous vehicles (AVs) are becoming increasingly prevalent. However, current AVs are unable to handle unexpected traffic signs (e.g., construction zones, road closures) encountered on the roads. To address this limitation, we propose MOSER, a Multimodal rOad Sign intERpretation system, to enable automated detection and interpretation of diverse road signs. Our system consists of a pipeline architecture with three main components, including perception, text processing, and planning. The perception component detects arbitrary road signs and extracts the sign text into proper groups and orders. The text processing component then identifies the high-level semantics of the text and determines whether any actions are required for the autonomous vehicle. Based on the interpretation of the signs, the planning component provides navigation guidance, such as instructing the vehicle to stop at a specific location or adding rules to its internal map. To the best of our knowledge, this is the first attempt to address the interpretation of arbitrary road signs using a multimodal processing strategy. Our work provides important insights and capabilities to support Level 4 autonomous vehicles, ensuring their safety and smoothness of operation.

Knowledge graph has been widely used in fact checking, owing to its capability to provide crucial background knowledge to help verify claims. Traditional fact checking works mainly focus on analyzing a single claim but have largely ignored analysis on the semantic consistency of pair-wise claims, despite its key importance in the real-world applications, e.g., multimodal fake news detection. This paper proposes a graph neural network based model INSPECTOR for pair-wise fact checking. Given a pair of claims, INSPECTOR aims to detect the potential semantic inconsistency of the input claims. The main idea of INSPECTOR is to use a graph attention neural network to learn a graph embedding for each claim in the pair, then use a tensor neural network to classify this pair of claims as consistent vs. inconsistent. The experiment results show that our algorithm outperforms state-of-the-art methods, with a higher accuracy and a lower variance.

Malicious cybersecurity activities have become increasingly worrisome for individuals and companies alike. While machine learning methods like Graph Neural Networks (GNNs) have proven successful on the malware detection task, their output is often difficult to understand. Explainable malware detection methods are needed to automatically identify malicious programs and present results to malware analysts in a way that is human interpretable. In this survey, we outline a number of GNN explainability methods and compare their performance on a real-world malware detection dataset. Specifically, we formulated the detection problem as a graph classification problem on the malware Control Flow Graphs (CFGs). We find that gradient-based methods outperform perturbation-based methods in terms of computational expense and performance on explainer-specific metrics (e.g., Fidelity and Sparsity). Our results provide insights into designing new GNN-based models for cyber malware detection and attribution.

Knowledge graph reasoning plays a pivotal role in many real-world applications, such as network alignment, computational fact-checking, recommendation, and many more. Among these applications, knowledge graph completion (KGC) and multi-hop question answering over knowledge graph (Multi-hop KGQA) are two representative reasoning tasks. In the vast majority of the existing works, the two tasks are considered separately with different models or algorithms. However, we envision that KGC and Multi-hop KGQA are closely related to each other. Therefore, the two tasks will benefit from each other if they are approached adequately. In this work, we propose a neural model named BiNet to jointly handle KGC and multi-hop KGQA, and formulate it as a multi-task learning problem. Specifically, our proposed model leverages a shared embedding space and an answer scoring module, which allows the two tasks to automatically share latent features and learn the interactions between natural language question decoder and answer scoring module. Compared to the existing methods, the proposed BiNet model addresses both multi-hop KGQA and KGC tasks simultaneously with superior performance. Experiment results show that BiNet outperforms state-of-the-art methods on a wide range of KGQA and KGC benchmark datasets.

Gaining timely insights on real-world emergency events, such as infectious disease outbreaks, is critical for developing appropriate response strategies. In this work, we propose a data-driven approach to study the spreading dynamics of the global Covid-19 pandemic. Specifically, we aim to identify a set of most “similar” geographic regions as proxies for making predictions on a targeted location. Example predictions include the number of new cases, number of hospitalizations, and number of deaths. Such predictions can be made at different levels of regional granularities, including city, county, and state levels. Our approach starts by transforming regional time series into graph representations using the natural visibility graph (NVG) model in order to capture their intrinsic trends and properties. These graphs are then projected onto a common embedding space using graph-level network embedding techniques. Essentially, each time series is converted as a data point in a feature embedding space, where spatial proximity indicates similarity among time series. Given a targeted region, our approach can identify the most “relevant” geographic regions by finding its k-nearest neighbors in the embedding space. Subsequently, appropriate response strategies and policies (e.g., school shutdown, indoor dining restriction) can be adapted based on the success or failure experiences from relevant regions. Our approach will potentially provide valuable insights in mitigating the spreading of infectious disease.

Network alignment, in general, seeks to discover the hidden underlying correspondence between nodes across two (or more) networks when given their network structure. However, most existing network alignment methods have added assumptions of additional constraints to guide the alignment, such as having a set of seed node-node correspondences across the networks or the existence of side-information. Instead, we seek to develop a general unsupervised network alignment algorithm that makes no additional assumptions. Recently, network embedding has proven effective in many network analysis tasks, but embeddings of different networks are not aligned. Thus, we present our Deep Adversarial Network Alignment (DANA) framework that first uses deep adversarial learning to discover complex mappings for aligning the embedding distributions of the two networks. Then, using our learned mapping functions, DANA performs an efficient nearest neighbor node alignment. Furthermore, we present an unsupervised heuristic to perform model selection for DANA. We perform experiments on real world datasets to show the effectiveness of our framework for first aligning the graph embedding distributions and then discovering node alignments that outperform existing methods.

Dense subgraph detection is a fundamental building block for a variety of applications. Most of the existing methods aim to discover dense subgraphs within either a single network or a multi-view network while ignoring the informative node dependencies across multiple layers of networks in a complex system. To date, it largely remains a daunting task to detect dense subgraphs on multi-layered networks. In this paper, we formulate the problem of dense subgraph detection on multi-layered networks based on cross-layer consistency principle. We further propose a novel algorithm DESTINE based on projected gradient descent with the following advantages. First, armed with the cross-layer dependencies, DESTINE is able to detect significantly more accurate and meaningful dense subgraphs at each layer. Second, it scales linearly w.r.t. the number of links in the multi-layered network. Extensive experiments demonstrate the efficacy of the proposed DESTINE algorithm in various cases.

Reasoning is a fundamental capability for harnessing valuable insight, knowledge and patterns from knowledge graphs. Existing work has primarily been focusing on point-wise reasoning, including search, link prediction, entity prediction, subgraph matching and so on. This paper introduces comparative reasoning over knowledge graphs, which aims to infer the commonality and inconsistency with respect to multiple pieces of clues. We envision that the comparative reasoning will complement and expand the existing point-wise reasoning over knowledge graphs. In detail, we develop KompaRe, the first of its kind prototype system that provides comparative reasoning capability over large knowledge graphs. We present both the system architecture and its core algorithms, including knowledge segment extraction, pairwise reasoning and collective reasoning. Empirical evaluations demonstrate the efficacy of the proposed KompaRe.

Subgraph Matching is one of the fundamental problems in network analysis, with a wide range of applications ranging from drug repurposing and discovery to programming language analysis. Due to the increasing prevalence of knowledge graphs (KGs), there has been growing interests in extending existing subgraph matching algorithms to the KG domain. One of the main challenges here lies on the structural gap, which refers to the difference between the query pattern and the corresponding subgraph instance due to variations in semantic expression. To address this challenge, we propose a semantic guided subgraph matching method for knowledge graphs, which extends our prior filtering-based method. Specifically, our approach leverages an external semantic ontology to estimate the overall fitness/quality of subgraph candidates with respect to the query template. In addition, our approach incorporates effective query decomposition strategies to reduce the overall query cost. Furthermore, we develop a distributed implementation of the algorithm such that it can be scaled up to handle knowledge graphs with a large number of entities and relations. We demonstrate the effectiveness of the proposed approach on a variety of semantic networks provided in the DARPA Modeling Adversarial Activity (MAA) program.

Networks are natural representations in modeling adversarial activities, such as smuggling, human trafficking, and illegal arms dealing. However, such activities are often covert and embedded across multiple domains and sources. They are generally not detectable and recognizable from the perspective of an isolated network, and only become apparent when multiple networks are analyzed in a unified m anner. T o t his e nd, we propose Complex Analytics of Network of Networks (CANON), a mathematical and computational framework for modeling adversarial activities from large-scale, multi-sourced data inputs. Central to our framework is a network-of-networks model, where nodes and edges can be defined across different domains and at multiple resolutions. Based on this model, we address the key challenges in modeling adversarial activities via four technical components, including optimization-based network alignment, network embedding and conditioning, approximate subgraph matching, and investigative subgraph discovery.In this paper, we describe the design and implementation of the individual components as well as integrating these components into a unified system using a modular microservice architecture. Extensive experiments have been conducted in both synthetics and real-world datasets to demonstrate the effectiveness of our proposed system under the DARPA Modeling Adversarial Activity (MAA) program.

Finding node associations across different networks is the cornerstone behind a wealth of high-impact data mining applications. Traditional approaches are often, explicitly or implicitly, built upon the linearity and/or consistency assumptions. On the other hand, the recent network embedding based methods promise a natural way to handle the non-linearity, yet they could suffer from the disparate node embedding space of different networks. In this paper, we address these limitations and tackle cross-network node associations from a new angle, i.e., cross-network transformation. We ask a generic question: Given two different networks, how can we transform one network to another? We propose an end-to-end model that learns a composition of nonlinear operations so that one network can be transformed to another in a hierarchical manner. The proposed model bears three distinctive advantages. First (composite transformation), it goes beyond the linearity/consistency assumptions and performs the cross-network transformation through a composition of nonlinear computations. Second (representation power), it can learn the transformation of both network structures and node attributes at different resolutions while identifying the cross-network node associations. Third (generality), it can be applied to various tasks, including network alignment, recommendation, cross-layer dependency inference. Extensive experiments on different tasks validate and verify the effectiveness of the proposed model.

Networks are prevalent in many areas and are often collected from multiple sources. However, due to the veracity characteristics, more often than not, networks are incomplete. Network alignment and network completion have become two fundamental cornerstones behind a wealth of high-impact graph mining applications. The state-of-the-art have been addressing these two tasks in parallel . That is, most of the existing network alignment methods have implicitly assumed that the topology of the input networks for alignment are perfectly known a priori, whereas the existing network completion methods admit either a single network (i.e., matrix completion) or multiple aligned networks (e.g., tensor completion). In this article, we argue that network alignment and completion are inherently complementary with each other, and hence propose to jointly address them so that the two tasks can mutually benefit from each other. We formulate the problem from the optimization perspective, and propose an effective algorithm ( iNeAt ) to solve it. The proposed method offers two distinctive advantages. First ( Alignment accuracy ), our method benefits from the higher-quality input networks while mitigates the effect of the incorrectly inferred links introduced by the completion task itself. Second ( Alignment efficiency ), thanks to the low-rank structure of the complete networks and the alignment matrix, the alignment process can be significantly accelerated. We perform extensive experiments which show that (1) the network completion can significantly improve the alignment accuracy, i.e., up to 30% over the baseline methods; (2) the network alignment can in turn help recover more missing edges than the baseline methods; and (3) our method achieves a good balance between the running time and the accuracy, and scales with a provable linear complexity in both time and space.

We study the problem of detecting matching subgraphs in a large multiplex background network based on predefined subgraph templates. Our approach extends existing filtering-based subgraph matching algorithms and proposes a new set of filters leveraging the monotone function properties in the multiplex setting. This enables effective pruning of irrelevant subgraph regions and expedites the overall matching process. In addition, our approach proposes a new strategy based on maximum likelihood estimate to identify “closely matched” subgraphs that are not isomorphic to the given templates from a noisy background network. This allows us to generalize this approach to real-world networks, which are often noisy, incomplete and ambiguous. We demonstrate the effectiveness of the proposed method on a real-world multiplex network provided by the DARPA Modeling Adversarial Activity (MAA) program. Our approach obtains highly accurate subgraph matching results for both the clean and noisy versions of the network, which significantly outperforms the baseline filtering methods. Furthermore, our proposed approach is parallelizable such that it can scale up to handle large input networks.

Subgraph matching is a core primitive across a number of disciplines, ranging from data mining, databases, information retrieval, computer vision to natural language processing. Despite decades of efforts, it is still highly challenging to balance between the matching accuracy and the computational efficiency, especially when the query graph and/or the data graph are large. In this paper, we propose an index-based algorithm (G-FINDER) to find the top-k approximate matching subgraphs. At the heart of the proposed algorithm are two techniques, including (1) a novel auxiliary data structure (LOOKUP-TABLE) in conjunction with a neighborhood expansion method to effectively and efficiently index candidate vertices, and (2) a dynamic filtering and refinement strategy to prune the false candidates at an early stage. The proposed G-FINDER bears some distinctive features, including (1) generality, being able to handle different types of inexact matching (e.g., missing nodes, missing edges, intermediate vertices) on node attributed and/or edge attributed graphs or multigraphs; (2) effectiveness, achieving up to 30% Fl-Score improvement over the best known competitor; and (3) efficiency, scaling near-linearly w.r.t. the size of the data graph as well as the query graph.

Network alignment is a fundamental task in many high-impact applications. Most of the existing approaches either explicitly or implicitly consider the alignment matrix as a linear transformation to map one network to another, and might overlook the complicated alignment relationship across networks. On the other hand, node representation learning based alignment methods are hampered by the incomparability among the node representations of different networks. In this paper, we propose a unified semi-supervised deep model (ORIGIN) that simultaneously finds the non-rigid network alignment and learns node representations in multiple networks in a mutually beneficial way. The key idea is to learn node representations by the effective graph convolutional networks, which subsequently enable us to formulate network alignment as a point set alignment problem. The proposed method offers two distinctive advantages. First (node representations), unlike the existing graph convolutional networks that aggregate the node information within a single network, we can effectively aggregate the auxiliary information from multiple sources, achieving far-reaching node representations. Second (network alignment), guided by the high-quality node representations, our proposed non-rigid point set alignment approach overcomes the bottleneck of the linear transformation assumption. We conduct extensive experiments that demonstrate the proposed non-rigid alignment method is (1) effective, outperforming both the state-of-the-art linear transformation-based methods and node representation based methods, and (2) efficient, with a comparable computational time between the proposed multi-network representation learning component and its single-network counterpart.

Graph data widely exist in many high-impact applications. Inspired by the success of deep learning in grid-structured data, graph neural network models have been proposed to learn powerful node-level or graph-level representation. However, most of the existing graph neural networks suffer from the following limitations: (1) there is limited analysis regarding the graph convolution properties, such as seed-oriented, degree-aware and order-free; (2) the node's degreespecific graph structure is not explicitly expressed in graph convolution for distinguishing structure-aware node neighborhoods; (3) the theoretical explanation regarding the graph-level pooling schemes is unclear.

Polarizing topics and events are often widely discussed and debated in social media, allowing researchers a unique view into the minds of large populations on everything from politics to entertainment. Previous work in identifying polarization in social media has largely used traditional community detection methods that are often confounded by the existence of neutral users and content. To address this problem, we propose a novel approach based on nonnegative matrix factorization (NMF) on a tripartite network to illuminate latent polarization patterns. The proposed methods are designed to work in contexts varying in the nature of the controversy, the level of polarization, the number of polarity groups involved and the presence of neutral entities. We use real-world Tumblr datasets to show that our algorithm exhibits superior performance in identifying polarization in online communities with respect to a range of real-world topics. To the best of our knowledge, our work is the first attempt to analyze polarization on the Tumblr platform.

Networks are natural analytic tools in modeling adversarial activities(e.g., human trafficking, illicit drug production, terrorist financial transaction) using different intelligence data sources. However, such activities are often covert and embedded across multiple domains and contexts. They are generally not detectable and recognizable from the perspective of an isolated network, and only become apparent when multiple networks are analyzed in a joint manner. Thus, one of the main research topics in modeling adversarial activities is to develop effective techniques to align and fuse information from different networks into a unified representation for global analysis. Based on the combined network representation, an equally important research topic is on detecting and matching indicating patterns to recognize the underlining adversarial activities in the integrated network. The focus of this workshop is to gather together the researchers from all relevant fields to share their experience and opinions on graph mining techniques in the era of big data, with emphasis on two fundamental problems - "Connecting the dots" and "finding a needle in a haystack", in the context of graph-based adversarial activity analytics.

How well can we predict which posts on social media platforms will eventually become popular? What approaches should we use to accomplish this task? In an era where human attention has become a commodity, the early detection of trending posts in online social media platforms is a problem of special importance, with applications ranging from business marketing to political campaigns and beyond. In this work we provide new insight towards tackling this problem by performing in-depth experiments on discovering trending posts on the popular mixed-media microblogging platform Tumblr. Inspired by prior art, our approach involves examining the key traits of the early adopters of online posts and utilizes a variety of network and temporal features to assist in performing classification. We obtain the complete data coverage of Tumblr for two consecutive months in order to study the characteristics and emerging patterns of popular posts. Based on the data, we investigate the interplay between the observation window of early adopters, the performance of individual classifiers, and the importance of various features. We find consistent trends where the importance of network features increases as the observation window increases, while the importance of content and temporal features decreases. To the best of our knowledge, this work is the first attempt to carry out a large-scale study on the early detection of trending posts on Tumblr.

Network alignment and network completion are two fundamental cornerstones behind many high-impact graph mining applications. The state-of-the-arts have been addressing these tasks in parallel. In this paper, we argue that network alignment and completion are inherently complementary with each other, and hence propose to jointly address them so that the two tasks can benefit from each other. We formulate it from the optimization perspective, and propose an effective algorithm iNEAT to solve it. The proposed method offers two distinctive advantages. First (Alignment accuracy), our method benefits from higher-quality input networks while mitigates the effect of incorrectly inferred links introduced by the completion task itself. Second (Alignment efficiency), thanks to the low-rank structure of the complete networks and alignment matrix, the alignment can be significantly accelerated. The extensive experiments demonstrate the performance of our algorithm.

The Islamic State of Iraq and Syria (ISIS) is a extremist militant group in the Middle East known to employ social media for propaganda and recruiting purposes. In particular, the social media website Twitter is well known to be exploited by ISIS supporters. To this end, we devise an effective and scalable classification scheme to filter out ISIS propaganda accounts from the rest of the Twitter accounts covering the general population in specific geographic regions. We take a data-driven approach to train and test a classifier using a combination of both content-based and network-based features on a large-scale dataset consisting of 10% random sample of all public Twitter posts in 2014. Such a dataset contains a total of 4,820 confirmed ISIS propaganda accounts and a large collection of general user accounts originated in nearby Egypt and Saudi Arabia regions. We show that high precision and specificity is obtained with the proposed classifier through cross-validation. In addition, we demonstrate that the use of network-based features derived from the Twitter @mention network is crucial on accurte classification of ISIS propaganda accounts.

We present the design and implementation of an automated event summarization system that leverages publicly available data from online sources. A novel Network of Networks (NoN) model is proposed to represent a multimodal data set comprising microblog posts, news articles, and images that describe current attitudes, trends, and events being shared by individuals and organizations. In this model, networks are arranged in layers that represent the different modalities, and the nodes within a given layer account for the information in that modality. Edges connect pairs of nodes - possibly from different modalities - based on the topical similarity of the content. A novel ranking algorithm is developed that selects a topically diverse collection of nodes across the different layers (i.e., tuples) that serve as representative highlights of the events described in the network. Tuples are subsequently stitched together in a temporal sequence in order to generate a consistent event storyline. This stitching is accomplished by framing the problem as a modified longest path problem in a directed acyclic graph. Our proposed system has been fully implemented using parallel computing paradigms for scalable data processing and real-time analysis, and initial experiments have been conducted on real-world events to demonstrate the effectiveness of the system.

Mining users'= topics of interest is one of the most important tasks for social media services. Given known topic associations for some fraction of the users in an online microblogging platform, our goal is to infer the topics of interest for the remaining users in the same site. Specifically, we proposed a novel bi-relational graph model to capture the interactions among users and their shared topics of interests. The proposed graph model contains two sub-graphs: one corresponds to users and the other corresponds to topics. Such a representation allows for effective exploitation of both user homophily relation and topic correlation simultaneously. This is in contrast with previous work where these two factors are considered in isolation. Subsequently, the user interest discovery problem is formulated as a multi-label learning problem on the bi-relational graph, with the goal to estimate the optimized associations between user nodes and topic nodes across the two sub-graphs. Our experiment is carried out with a complete month-long data collected from Twitter and Tumblr via GNIP Decahose1and Firehose2respectively. The large-scale studies shed light on the effectiveness of inferring user interests based on the underlying social connections.