We present a novel end-to-end framework that generates highly compact (typically 6-15 dimensions), discrete (int4 type), and interpretable node representations—termed node identifiers (node IDs)—to tackle inference challenges on large-scale graphs. By employing vector quantization, we compress continuous node embeddings from multiple layers of a Graph Neural Network (GNN) into discrete codes, applicable under both self-supervised and supervised learning paradigms. These node IDs capture high-level abstractions of graph data and offer interpretability that traditional GNN embeddings lack. Extensive experiments on 34 datasets, encompassing node classification, graph classification, link prediction, and attributed graph clustering tasks, demonstrate that the generated node IDs significantly enhance speed and memory efficiency while achieving competitive performance compared to current state-of-the-art methods. Our source code is available at https://github.com/LUOyk1999/NodeID.

Message-passing Graph Neural Networks (GNNs) are often criticized for their limited expressiveness, issues like over-smoothing and over-squashing, and challenges in capturing long-range dependencies. Conversely, Graph Transformers (GTs) are regarded as superior due to their employment of global attention mechanisms, which potentially mitigate these challenges. Literature frequently suggests that GTs outperform GNNs in graph-level tasks, especially for graph classification and regression on small molecular graphs. In this study, we explore the untapped potential of GNNs through an enhanced framework, GNN+, which integrates six widely used techniques: edge feature integration, normalization, dropout, residual connections, feed-forward networks, and positional encoding, to effectively tackle graph-level tasks. We conduct a systematic re-evaluation of three classic GNNs—GCN, GIN, and GatedGCN—enhanced by the GNN+ framework across 14 well-known graph-level datasets. Our results reveal that, contrary to prevailing beliefs, these classic GNNs consistently match or surpass the performance of GTs, securing top-three rankings across all datasets and achieving first place in eight. Furthermore, they demonstrate greater efficiency, running several times faster than GTs on many datasets. This highlights the potential of simple GNN architectures, challenging the notion that complex mechanisms in GTs are essential for superior graph-level performance. Our source code is available at https://github.com/LUOyk1999/GNNPlus.

Landslides pose severe threats to infrastructure and safety, and their segmentation in remote sensing imagery remains challenging due to irregular boundaries, scale variation, and complex terrain. Traditional lightweight models often struggle to capture rich semantic features under these conditions. To address this, we leverage vision foundation models (VFMs) as teachers and propose a knowledge distillation adversarial (KDA) framework to transfer high-capacity knowledge into compact student models. Additionally, we introduce a dynamic cross-layer fusion (DCF) decoder to enhance global–local feature interaction. The experimental results demonstrate that, compared to the previous best-performing model SegNeXt [89.92% precision and 84.78% mean intersection over union (mIoU)], our method achieves a precision of 91.93% and mIoU of 86.53%, yielding improvements of 2.01% and 1.75%, respectively. Source code is available athttps://github.com/PreWisdom/KDA

Link prediction (LP) is crucial for Knowledge Graphs (KG) completion but commonly suffers from interpretability issues. While several methods have been proposed to explain embedding-based LP models, they are generally limited to local explanations on KG and are deficient in providing human interpretable semantics. Based on real-world observations of the characteristics of KGs from multiple domains, we propose to explain LP models in KG with path-based explanations. An integrated framework, namely eXpath, is introduced which incorporates the concept of relation path with ontological closed path rules to enhance both the efficiency and effectiveness of LP interpretation. Notably, the eXpath explanations can be fused with other single-link explanation approaches to achieve a better overall solution. Extensive experiments across benchmark datasets and LP models demonstrate that introducing eXpath can boost the quality of resulting explanations by about 20% on two key metrics and reduce the required explanation time by 61.4%, in comparison to the best existing method. Case studies further highlight eXpath's ability to provide more semantically meaningful explanations through path-based evidence.

Understanding the evolution of scholarly research is essential for many real-life decision-making processes in academia, such as research planning, frontier exploration, and award selection. Popular platforms like Google Scholar and Web of Science rely on numerical indicators that are too abstract to convey the context and content of scientific research, while most existing visualization approaches on mapping science do not consider the presentation of individual scholars' research evolution using curated self-citation data. This paper builds on our previous work and proposes an integrated pipeline to visualize a scholar's research evolution from multiple topic facets. A novel 3D prism-shaped visual metaphor is introduced as the overview of a scholar's research profile, whilst their scientific evolution on each topic is displayed in a more structured manner. Additional designs by topic chord diagram, streamgraph visualization, and inter-topic flow map, optimized by an elaborate layout algorithm, assist in perceiving the scholar's scientific evolution across topics. A new six-degree-impact glyph metaphor highlights key interdisciplinary works driving the evolution. The proposed visualization methods are evaluated through case studies analyzing the careers of prestigious Turing award laureates, one major visualization venue, and a focused user study.

Self-Supervised Learning (SSL) methods harness the concept of semantic invariance by utilizing data augmentation strategies to produce similar representations for different deformations of the same input. Essentially, the model captures the shared information among multiple augmented views of samples, while disregarding the non-shared information that may be beneficial for downstream tasks. To address this issue, we introduce a module called CompMod with Meta Comprehensive Regularization (MCR), embedded into existing self-supervised frameworks, to make the learned representations more comprehensive. Specifically, we update our proposed model through a bi-level optimization mechanism, enabling it to capture comprehensive features. Additionally, guided by the constrained extraction of features using maximum entropy coding, the self-supervised learning model learns more comprehensive features on top of learning consistent features. In addition, we provide theoretical support for our proposed method from information theory and causal counterfactual perspective. Experimental results show that our method achieves significant improvement in classification, object detection and semantic segmentation tasks on multiple benchmark datasets.

Explaining the decisions made by Graph Neural Networks (GNNs) is vital for establishing trust and ensuring fairness in critical applications such as medicine and science. The prevalence of hierarchical structure in real-world graphs/networks raises an important question on GNN interpretability: "On each level of the graph structure, which specific fraction imposes the highest influence over the prediction?" Currently, the prevailing two categories of methods are incapable of achieving multi-level GNN explanation due to their flat or motif-centric nature. In this work, we formulate the problem of learning multi-level explanations out of GNN models and introduce a stratified explainer module, namely STFExplainer, that utilizes the concept of sufficient expansion to generate explanations on each stratum. Specifically, we learn a higher-level subgraph generator by leveraging both hierarchical structure and GNN-encoded input features. Experiment results on both synthetic and real-world datasets demonstrate the superiority of our stratified explainer on standard interpretability tasks and metrics such as fidelity and explanation recall, with an average improvement of 11% and 8% over the best alternative on each data type. The case study on material domains also confirms the value of our approach through detected multi-level graph patterns accurately reconstructing the knowledge-based ground truth.

Graph Transformers (GTs) have recently emerged as popular alternatives to traditional message-passing Graph Neural Networks (GNNs), due to their theoretically superior expressiveness and impressive performance reported on standard node classification benchmarks, often significantly outperforming GNNs. In this paper, we conduct a thorough empirical analysis to reevaluate the performance of three classic GNN models (GCN, GAT, and GraphSAGE) against GTs. Our findings suggest that the previously reported superiority of GTs may have been overstated due to suboptimal hyperparameter configurations in GNNs. Remarkably, with slight hyperparameter tuning, these classic GNN models achieve state-of-the-art performance, matching or even exceeding that of recent GTs across 17 out of the 18 diverse datasets examined. Additionally, we conduct detailed ablation studies to investigate the influence of various GNN configurations—such as normalization, dropout, residual connections, and network depth—on node classification performance. Our study aims to promote a higher standard of empirical rigor in the field of graph machine learning, encouraging more accurate comparisons and evaluations of model capabilities. Our implementation is available at https://github.com/LUOyk1999/tunedGNN.

Graph transformers need strong inductive biases to derive meaningful attention scores. Yet, current methods often fall short in capturing longer ranges, hierarchical structures, or community structures, which are common in various graphs such as molecules, social networks, and citation networks. This paper presents a Hierarchical Distance Structural Encoding (HDSE) method to model node distances in a graph, focusing on its multi-level, hierarchical nature. We introduce a novel framework to seamlessly integrate HDSE into the attention mechanism of existing graph transformers, allowing for simultaneous application with other positional encodings. To apply graph transformers with HDSE to large-scale graphs, we further propose a high-level HDSE that effectively biases the linear transformers towards graph hierarchies. We theoretically prove the superiority of HDSE in terms of expressivity and generalization. Empirically, we demonstrate that graph transformers with HDSE excel in graph classification, regression on 7 graph-level datasets, and node classification on 11 large-scale graphs.

Smart city situational awareness has recently emerged as a hot topic in research societies, industries, and governments because of its potential to integrate cutting-edge information technology and solve urgent challenges that modern cities face. For example, in the latest five-year plan, the Chinese government has highlighted the demand to empower smart city management with new technologies such as big data and Internet of Things, for which situational awareness is normally the crucial first step. While traditional static surveillance data on cities have been available for decades, this review reports a type of relatively new yet highly important urban data source, i.e., the big mobile data collected by devices with various levels of mobility representing the movement and distribution of public and private agents in the city. We especially focus on smart city situational awareness enabled by synthesizing the localization of hundreds of thousands of mobile software Apps using the Global Positioning System (GPS). This technique enjoys advantages such as a large penetration rate (∼50% urban population covered), uniform spatiotemporal coverage, and high localization precision. We first discuss the pragmatic requirements for smart city situational awareness and the challenges faced. Then we introduce two suites of empowering technologies that help fulfill the requirements of (1) cybersecurity insurance for smart cities and (2) spatiotemporal modeling and visualization for situational awareness, both via big mobile data. The main contributions of this review lie in the description of a comprehensive technological framework for smart city situational awareness and the demonstration of its feasibility via real-world applications.

Unsupervised learning has received more attention due to the superior performance of contrastive learning methods. Most contrastive methods use data augmentation techniques to construct positive and negative pairs. The augmented view of the same sample is regarded as a positive sample, while the rest are negative samples. This negative sampling strategy has strong randomness and ignores samples that are semantically similar to anchors, namely sampling bias. This problem has been addressed by weighting the similarity of negative samples. In this paper, we propose a novel ultimate negative sampling for contrastive learning. Unlike random sampling, we set a more extreme negative sample selection mechanism based on the ideal representation of the sample. Furthermore, we constrain the consistency between samples across the space. Experiment results demonstrate the proposed method’s superiority on multiple benchmark datasets.

Quantitatively profiling a scholar's scientific impact is important to modern research society. Current practices with bibliometric indicators (e.g., h-index), lists, and networks perform well at scholar ranking, but do not provide structured context for scholar-centric, analytical tasks such as profile reasoning and understanding. This work presents GeneticFlow (GF), a suite of novel graph-based scholar profiles that fulfill three essential requirements: structured-context, scholar-centric, and evolution-rich. We propose a framework to compute GF over large-scale academic data sources with millions of scholars. The framework encompasses a new unsupervised advisor-advisee detection algorithm, a well-engineered citation type classifier using interpretable features, and a fine-tuned graph neural network (GNN) model. Evaluations are conducted on the real-world task of scientific award inference. Experiment outcomes show that the F1 score of best GF profile significantly outperforms alternative methods of impact indicators and bibliometric networks in all the 6 computer science fields considered. Moreover, the core GF profiles, with 63.6%\sim66.5% nodes and 12.5%\sim29.9% edges of the full profile, still significantly outrun existing methods in 5 out of 6 fields studied. Visualization of GF profiling result also reveals human explainable patterns for high-impact scholars.

Self-supervised learning (SSL) has great potential for molecular representation learning given the complexity of molecular graphs, the large amounts of unlabelled data available, the considerable cost of obtaining labels experimentally, and the hence often only small training datasets. The importance of the topic is reflected in the variety of paradigms and architectures that have been investigated recently, most focus on designing views for contrastive learning. In this paper, we study SSL based on persistent homology (PH), a mathematical tool for modeling topological features of data that persist across multiple scales. It has several unique features which particularly suit SSL, naturally offering: different views of the data, stability in terms of distance preservation, and the opportunity to flexibly incorporate domain knowledge. We (1) investigate an autoencoder, which shows the general representational power of PH, and (2) propose a contrastive loss that complements existing approaches. We rigorously evaluate our approach for molecular property prediction and demonstrate its particular features in improving the embedding space: after SSL, the representations are better and offer considerably more predictive power than the baselines over different probing tasks; our loss increases baseline performance, sometimes largely; and we often obtain substantial improvements over very small datasets, a common scenario in practice.

Transformer models have recently gained popularity in graph representation learning as they have the potential to learn complex relationships beyond the ones captured by regular graph neural networks. The main research question is how to inject the structural bias of graphs into the transformer architecture, and several proposals have been made for undirected molecular graphs and, recently, also for larger network graphs. In this paper, we study transformers over directed acyclic graphs (DAGs) and propose architecture adaptations tailored to DAGs: (1) An attention mechanism that is considerably more efficient than the regular quadratic complexity of transformers and at the same time faithfully captures the DAG structure, and (2) a positional encoding of the DAG's partial order, complementing the former. We rigorously evaluate our approach over various types of tasks, ranging from classifying source code graphs to nodes in citation networks, and show that it is effective in two important aspects: in making graph transformers generally outperform graph neural networks tailored to DAGs and in improving SOTA graph transformer performance in terms of both quality and efficiency.

Analyzing the urban trajectory in cities has become an important topic in data mining. How can we model the human mobility consisting of stay and travel states from the raw trajectory data? How can we infer these mobility states from a single user’s trajectory information? How can we further generalize the mobility inference to the real-world trajectory data that span multiple users and are sparsely sampled over time? In this article, based on formal and rigid definitions of the stay/travel mobility, we propose a single trajectory inference algorithm that utilizes a generic long-tailed sparsity pattern in the large-scale trajectory data. The algorithm guarantees a 100% precision in the stay/travel inference with a provable lower bound in the recall metric. Furthermore, we design a transformer-like deep learning architecture on the problem of mobility inference from multiple sparse trajectories. Several adaptations from the standard transformer network structure are introduced, including the singleton design to avoid the negative effect of sparse labels in the decoder side, the customized space-time embedding on features of location records, and the mask apparatus at the output side for loss function correction. Evaluations on three trajectory datasets of 40 million urban users validate the performance guarantees of the proposed inference algorithm and demonstrate the superiority of our deep learning model, in comparison to sequence learning methods in the literature. On extremely sparse trajectories, the deep learning model improves from the single trajectory inference algorithm with more than two times of overall and F1 accuracy. The model also generalizes to large-scale trajectory data from different sources with good scalability.

Visually identifying effective bio-markers from human brain networks poses non-trivial challenges to the field of data visualization and analysis. Existing methods in the literature and neuroscience practice are generally limited to the study of individual connectivity features in the brain (e.g., the strength of neural connection among brain regions). Pairwise comparisons between contrasting subject groups (e.g., the diseased and the healthy controls) are normally performed. The underlying neuroimaging and brain network construction process is assumed to have 100% fidelity. Yet, real-world user requirements on brain network visual comparison lean against these assumptions. In this work, we present MV^2Net, a visual analytics system that tightly integrates multi-variate multi-view visualization for brain network comparison with an interactive wrangling mechanism to deal with data uncertainty. On the analysis side, the system integrates multiple extraction methods on diffusion and geometric connectivity features of brain networks, an anomaly detection algorithm for data quality assessment, single- and multi-connection feature selection methods for bio-marker detection. On the visualization side, novel designs are introduced which optimize network comparisons among contrasting subject groups and related connectivity features. Our design provides level-of-detail comparisons, from juxtaposed and explicit-coding views for subject group comparisons, to high-order composite view for correlation of network comparisons, and to fiber tract detail view for voxel-level comparisons. The proposed techniques are inspired and evaluated in expert studies, as well as through case analyses on diffusion and geometric bio-markers of certain neurology diseases. Results in these experiments demonstrate the effectiveness and superiority of MV^2Net over state-of-the-art approaches.

Inspired by the success of BERT, several multimodal representation learning approaches have been proposed that jointly represent image and text. These approaches achieve superior performance by capturing high-level semantic information from large-scale multimodal pretraining. In particular, LXMERT and UNITER adopt visual region feature regression and label classification as pretext tasks. However, they tend to suffer from the problems of noisy labels and sparse semantic annotations, based on the visual features having been pretrained on a crowdsourced dataset with limited and inconsistent semantic labeling. To overcome these issues, we propose unbiased Dense Contrastive Visual-Linguistic Pretraining (DCVLP), which replaces the region regression and classification with cross-modality region contrastive learning that requires no annotations. Two data augmentation strategies (Mask Perturbation and Intra-Inter-Adversarial Perturbation) are developed to improve the quality of negative samples used in contrastive learning. Overall, DCVLP allows cross-modality dense region contrastive learning in a self-supervised setting independent of any object annotations. We compare our method against prior visual-linguistic pretraining frameworks to validate the superiority of dense contrastive learning on multimodal representation learning.

Visualizing massive scale human movement in cities plays an important role in solving many of the problems that modern cities face (e.g., traffic optimization, business site configuration). In this article, we study a big mobile location dataset that covers millions of city residents, but is temporally sparse on the trajectory of individual user. Mapping sparse trajectories to illustrate population movement poses several challenges from both analysis and visualization perspectives. In the literature, there are a few techniques designed for sparse trajectory visualization; yet they do not consider trajectories collected from mobile apps that possess long-tailed sparsity with record intervals as long as hours. This article introduces UrbanMotion, a visual analytics system that extends the original wind map design by supporting map-matched local movements, multi-directional population flows, and population distributions. Effective methods are proposed to extract and aggregate population movements from dense parts of the trajectories leveraging their long-tailed sparsity. Both characteristic and anomalous patterns are discovered and visualized. We conducted three case studies, one comparative experiment, and collected expert feedback in the application domains of commuting analysis, event detection, and business site configuration. The study result demonstrates the significance and effectiveness of our system in helping to complete key analytics tasks for urban users.

Online fraud is the well-known dark side of the modern Internet. Unsupervised fraud detection algorithms are widely used to address this problem. However, selecting features, adjusting hyperparameters, evaluating the algorithms, and eliminating false positives all require human expert involvement. In this work, we design and implement an end-to-end interactive visualization system, FDHelper, based on the deep understanding of the mechanism of the black market and fraud detection algorithms. We identify a workflow based on experience from both fraud detection algorithm experts and domain experts. Using a multi-granularity three-layer visualization map embedding an entropy-based distance metric ColDis, analysts can interactively select different feature sets, refine fraud detection algorithms, tune parameters and evaluate the detection result in near real-time. We demonstrate the effectiveness and significance of FDHelper through two case studies with state-of-the-art fraud detection algorithms, interviews with domain experts and algorithm experts, and a user study with eight first-time end users.

Multi-modality fusion technologies have greatly improved the performance of neural network-based Video Description/Caption, Visual Question Answering (VQA) and Audio Visual Scene-aware Dialog (AVSD) over the recent years. Most previous approaches only explore the last layers of multiple layer feature fusion while omitting the importance of intermediate layers. To solve the issue for the intermediate layers, we propose an efficient Quaternion Block Network (QBN) to learn interaction not only for the last layer but also for all intermediate layers simultaneously. In our proposed QBN, we use the holistic text features to guide the update of visual features. In the meantime, Hamilton quaternion products can efficiently perform information flow from higher layers to lower layers for both visual and text modalities. The evaluation results show our QBN improve the performance on VQA 2.0, furthermore surpasses the approach using large scale BERT or visual BERT pre-trained models. Extensive ablation study has been carried out to examine the influence of each proposed module in this study.

The visualization of evolutionary influence graphs is important for performing many real-life tasks such as citation analysis and social influence analysis. The main challenges include how to summarize large-scale, complex, and time-evolving influence graphs, and how to design effective visual metaphors and dynamic representation methods to illustrate influence patterns over time. In this work, we present Eiffel, an integrated visual analytics system that applies triple summarizations on evolutionary influence graphs in the nodal, relational, and temporal dimensions. In numerical experiments, Eiffel summarization results outperformed those of traditional clustering algorithms with respect to the influence-flow-based objective. Moreover, a flow map representation is proposed and adapted to the case of influence graph summarization, which supports two modes of evolutionary visualization (i.e., flip-book and movie) to expedite the analysis of influence graph dynamics. We conducted two controlled user experiments to evaluate our technique on influence graph summarization and visualization respectively. We also showcased the system in the evolutionary influence analysis of two typical scenarios, the citation influence of scientific papers and the social influence of emerging online events. The evaluation results demonstrate the value of Eiffel in the visual analysis of evolutionary influence graphs.

Successfully detecting, analyzing, and reasoning about collective anomalies is important for many real-life application domains (e.g., intrusion detection, fraud analysis, software security). The primary challenges to achieving this goal include the overwhelming number of low-risk events and their multimodal relationships, the diversity of collective anomalies by various data and anomaly types, and the difficulty in incorporating the domain knowledge of experts. In this paper, we propose the novel concept of the faceted High-Order Correlation Graph (HOCG). Compared with previous, low-order correlation graphs, HOCG achieves better user interactivity, computational scalability, and domain generality through synthesizing heterogeneous types of objects, their anomalies, and the multimodal relationships, all in a single graph. We design elaborate visual metaphors, interaction models, and the coordinated multiple view based interface to allow users to fully unleash the visual analytics power of the HOCG. We conduct case studies for three application domains and collect feedback from domain experts who apply our method to these scenarios. The results demonstrate the effectiveness of the HOCG in the overview of point anomalies, the detection of collective anomalies, and the reasoning process of root cause analyses.

Hierarchical abstraction is a scalable strategy to deal with large networks. Existing visualization methods have allowed to aggregate the network nodes into hierarchies based on the node attributes or network topology, each of which has its own advantage. Very few previous system has the capability to enjoy the best of both worlds. This paper presents OnionGraph, an integrated framework for the exploratory visual analysis of heterogeneous multivariate networks. OnionGraph allows nodes to be aggregated based on either node attributes, topology, or a hierarchical combination of both. These aggregations can be split, merged and filtered under the focus+context interaction model, or automatically traversed by the information-theoretic navigation method. Node aggregations that contain subsets of nodes are displayed by the onion metaphor, indicating the level and details of the abstraction. We have evaluated the OnionGraph tool in three real-world cases. Performance experiments demonstrate that on a commodity desktop, our method can scale to million-node networks while preserving the interactivity for analysis.

Online question pools like LeetCode provide hands-on exercises of skills and knowledge. However, due to the large volume of questions and the intent of hiding the tested knowledge behind them, many users find it hard to decide where to start or how to proceed based on their goals and performance. To overcome these limitations, we present PeerLens, an interactive visual analysis system that enables peer-inspired learning path planning. PeerLens can recommend a customized, adaptable sequence of practice questions to individual learners, based on the exercise history of other users in a similar learning scenario. We propose a new way to model the learning path by submission types and a novel visual design to facilitate the understanding and planning of the learning path. We conducted a within-subject experiment to assess the efficacy and usefulness of PeerLens in comparison with two baseline systems. Experiment results show that users are more confident in arranging their learning path via PeerLens and find it more informative and intuitive.

Multi-set query is a fundamental issue in data science. When the sizes of multi-sets are large, exact matching methods like hash tables need too much memory, and they cannot achieve high query speed. Bloom filters are recently used to handle big data query, but they cannot achieve high accuracy when the memory space is tight. In this paper, we propose a new data structure named coloring embedder, which is fast, accurate as well as memory efficient. The insight is to first map elements to a high dimensional space to almost eliminate hashing collisions, and then use a dimensional reduction representation, which is similar to coloring a graph, to save memory. Theoretical proofs and experimental results show that compared to the state-of-the[1]art, the error rate of the coloring embedder is thousands of times smaller even with much less memory usage, and the query speed of the coloring embedder is about 2 times faster. The source code of coloring embedder is released on Github.

<?tight?>Discovering the correlations among variables of air quality data is challenging, because the correlation time series are long-lasting, multi-faceted, and information-sparse. In this article, we propose a novel visual representation, called Time-correlation-partitioning (TCP) tree, that compactly characterizes correlations of multiple air quality variables and their evolutions. A TCP tree is generated by partitioning the information-theoretic correlation time series into pieces with respect to the variable hierarchy and temporal variations, and reorganizing these pieces into a hierarchically nested structure. The visual exploration of a TCP tree provides a sparse data traversal of the correlation variations and a situation-aware analysis of correlations among variables. This can help meteorologists understand the correlations among air quality variables better. We demonstrate the efficiency of our approach in a real-world air quality investigation scenario.

The recent advance of deep learning has enabled trading algorithms to predict stock price movements more accurately. Unfortunately, there is a significant gap in the real-world deployment of this breakthrough. For example, professional traders in their long-term careers have accumulated numerous trading rules, the myth of which they can understand quite well. On the other hand, deep learning models have been hardly interpretable. This paper presents DeepClue, a system built to bridge text-based deep learning models and end users through visually interpreting the key factors learned in the stock price prediction model. We make three contributions in DeepClue. First, by designing the deep neural network architecture for interpretation and applying an algorithm to extract relevant predictive factors, we provide a useful case on what can be interpreted out of the prediction model for end users. Second, by exploring hierarchies over the extracted factors and displaying these factors in an interactive, hierarchical visualization interface, we shed light on how to effectively communicate the interpreted model to end users. Specially, the interpretation separates the predictables from the unpredictables for stock prediction through the use of intercept model parameters and a risk visualization design. Third, we evaluate the integrated visualization system through two case studies in predicting the stock price with financial news and company-related tweets from social media. Quantitative experiments comparing the proposed neural network architecture with state-of-the-art models and the human baseline are conducted and reported. Feedbacks from an informal user study with domain experts are summarized and discussed in details. The study results demonstrate the effectiveness of DeepClue in helping to complete stock market investment and analysis tasks.

Drawings of non-planar graphs always result in edge crossings. When there are many edges crossing at small angles, it is often difficult to follow these edges, because of the multiple visual paths resulted from the crossings that slow down eye movements. In this paper we propose an algorithm that disambiguates the edges with automatic selection of distinctive colors. Our proposed algorithm computes a near optimal color assignment of a dual collision graph, using a novel branch-and-bound procedure applied to a space decomposition of the color gamut. We give examples demonstrating this approach in real world graphs and maps, as well as a user study to establish its effectiveness and limitations.

Discovering fraud user behaviors is vital to keeping online websites healthy. Fraudsters usually exhibit grouping behaviors, and researchers have effectively leveraged this behavior to design unsupervised algorithms to detect fraud user groups. In this work, we propose a visualization system, FraudVis, to visually analyze the unsupervised fraud detection algorithms from temporal, intra-group correlation, inter-group correlation, feature selection, and the individual user perspectives. FraudVis helps domain experts better understand the algorithm output and the detected fraud behaviors. Meanwhile, FraudVis also helps algorithm experts to fine-tune the algorithm design through the visual comparison. By using the visualization system, we solve two real-world cases of fraud detection, one for a social video website and another for an e-commerce website. The results on both cases demonstrate the effectiveness of FraudVis in understanding unsupervised fraud detection algorithms.

Detecting, analyzing and reasoning collective anomalies is important for many real-life application domains such as facility monitoring, software analysis and security. The main challenges include the overwhelming number of low-risk events and their multifaceted relationships which form the collective anomaly, the diversity in various data and anomaly types, and the difficulty to incorporate domain knowledge in the anomaly analysis process. In this paper, we propose a novel concept of high-order correlation graph (HOCG). Compared with the previous correlation graph definition, HOCG achieves better user interactivity, computational scalability, and domain generality through synthesizing heterogeneous types of nodes, attributes, and multifaceted relationships in a single graph. We design elaborate visual metaphors, interaction models, and the coordinated multiple view based interface to allow users to fully unleash the visual analytics power over HOCG. We conduct case studies in two real-life application domains, i.e., facility monitoring and software analysis. The results demonstrate the effectiveness of HOCG in the overview of point anomalies, detection of collective anomalies, and reasoning process of root cause analysis.

Data stream processing is a fundamental issue in many fields, such as data mining, databases, network traffic measurement. There are five typical tasks in data stream processing: frequency estimation, heavy hitter detection, heavy change detection, frequency distribution estimation, and entropy estimation. Different algorithms are proposed for different tasks, but they seldom achieve high accuracy and high speed at the same time. To address this issue, we propose a novel data structure named HeavyGuardian. The key idea is to intelligently separate and guard the information of hot items while approximately record the frequencies of cold items. We deploy HeavyGuardian on the above five typical tasks. Extensive experimental results show that HeavyGuardian achieves both much higher accuracy and higher speed than the state-of-the-art solutions for each of the five typical tasks. The source codes of HeavyGuardian and other related algorithms are available at GitHub.

Studies of the human brain network are becoming increasingly popular in the fields of neuroscience, computer science, and neurology. Despite this rapidly growing line of research, gaps remain on the intersection of data analytics, interactive visual representation, and the human intelligence—all needed to advance our understanding of human brain networks. This article tackles this challenge by exploring the design space of visual analytics. We propose an integrated framework to orchestrate computational models with comprehensive data visualizations on the human brain network. The framework targets two fundamental tasks: the visual exploration of multi-label brain networks and the visual comparison among brain networks across different subject groups. During the first task, we propose a novel interactive user interface to visualize sets of labeled brain networks; in our second task, we introduce sparse regression models to select discriminative features from the brain network to facilitate the comparison. Through user studies and quantitative experiments, both methods are shown to greatly improve the visual comparison performance. Finally, real-world case studies with domain experts demonstrate the utility and effectiveness of our framework to analyze reconstructions of human brain connectivity maps. The perceptually optimized visualization design and the feature selection model calibration are shown to be the key to our significant findings.

Visual exploration of flow fields is important for studying dynamic systems. We introduce semantic flow graph (SFG), a novel graph representation and interaction framework that enables users to explore the relationships among key objects (i.e., field lines, features, and spatiotemporal regions) of both steady and unsteady flow fields. The objects and their relationships are organized as a heterogeneous graph. We assign each object a set of attributes, based on which a semantic abstraction of the heterogeneous graph is generated. This semantic abstraction is SFG. We design a suite of operations to explore the underlying flow fields based on this graph representation and abstraction mechanism. Users can flexibly reconfigure SFG to examine the relationships among groups of objects at different abstraction levels. Three linked views are developed to display SFG, its node split criteria and history, and the objects in the spatial volume. For simplicity, we introduce SFG construction and exploration for steady flow fields with critical points being the only features. Then we demonstrate that SFG can be naturally extended to deal with unsteady flow fields and multiple types of features. We experiment with multiple data sets and conduct an expert evaluation to demonstrate the effectiveness of our approach.

Deep learning has achieved impressive success in a variety of tasks and is developing rapidly in recent years. The problem of understanding the deep learning models has become an issue for the development of deep learning, for example, in domains like medicine and finance which require interpretable models. While it is challenging to analyze and interpret complicated deep neural networks, visualization is good at bridging between abstract data and intuitive representations. Visual analytics for deep learning is a rapidly growing research field. To help users better understand this field, we present a mini-survey including a user-based taxonomy that covers state-of-the-art works of the field. Regarding the requirements of different types of users (beginners, practitioners, developers, and experts), we categorize the methods and tools by four visualization goals respectively focusing on teaching deep learning concepts, architecture assessment, tools for debugging and improving models, and visual explanation. Notably, we present a table consisting of the name of the method or tool, the year, the visualization goal, and the types of networks to which the method or tool can be applied, to assist users in finding available tools and methods quickly. To emphasize the importance of visual explanation for deep learning, we introduce the studies in this research field in detail.

Visually comparing human brain networks from multiple population groups serves as an important task in the field of brain connectomics. The commonly used brain network representation, consisting of nodes and edges, may not be able to reveal the most compelling network differences when the reconstructed networks are dense and homogeneous. In this paper, we leveraged the block information on the Region Of Interest (ROI) based brain networks and studied the problem of blockwise brain network visual comparison. An integrated visual analytics framework was proposed. In the first stage, a two-level ROI block hierarchy was detected by optimizing the anatomical structure and the predictive comparison performance simultaneously. In the second stage, the NodeTrix representation was adopted and customized to visualize the brain network with block information. We conducted controlled user experiments and case studies to evaluate our proposed solution. Results indicated that our visual analytics method outperformed the commonly used node-link graph and adjacency matrix design in the blockwise network comparison tasks. We have shown compelling findings from two real-world brain network data sets, which are consistent with the prior connectomics studies.

The theme of this workshop is to bridge data mining and visual analytics for information and knowledge management. The topics include, but not limited to, the following: Big data mining and visual analytics, theory and foundations -- Knowledge discovery with data mining and visual analytics technologies -- Fusion, mining and visualization of rich and heterogeneous data source -- Security and privacy issues in data mining and visual analytics systems -- Information, social and biological graph mining and visualization -- Novel methods on visualization-oriented data mining -- Visual representations and interaction techniques of data mining results -- Data management and knowledge representation including scalable data representations -- Mathematical foundations and algorithms in data mining to allow interactive visual analysis -- Analytical reasoning including the human analytic, knowledge discovery, perception, and collaborative visual analytics -- Evaluation methods for data mining algorithms and visual analytics systems -- Applications of visual analytics and data mining techniques, including but not limited to applications in science, engineering, public safety, commerce, etc.

Summarizing large influence graphs is crucial for many graph visualization and mining tasks. Classical graph clustering and compression algorithms focus on summarizing the nodes by their structural-level or attribute-level similarities, but usually are not designed to characterize the flow-level pattern which is the centerpiece of influence graphs. On the other hand, the social influence analysis has been intensively studied, but little is done on the summarization problem without an explicit focus on social networks. Building on the recent study of the Influence Graph Summarization (IGS), this paper presents a new perspective of the underlying flow-based heuristic. It establishes a direct linkage between the optimal summarization and the classic eigenvector centrality of the graph nodes. Such a theoretic linkage has important implications on numerous aspects in the pursuit of a perfect influence graph summarization. In particular, it enables us to develop a suite of algorithms that can: 1) achieve a near-optimal IGS objective, 2) support dynamic summarizations balancing the IGS objective and the stability of transition in navigating the summarization, and 3) scale to million-node graphs with a near-linear computational complexity. Both quantitative experiments on real-world citation networks and the user studies on the task analysis experience demonstrate the effectiveness of the proposed summarization algorithms.

Why are some people more creative than others? How do human brain networks evolve over time? A key stepping stone to both mysteries and many more is to compare weighted brain networks. In contrast to networks arising from other application domains, the brain network exhibits its own characteristics (e.g., high density, indistinguishability), which makes any off-the-shelf data mining algorithm as well as visualization tool sub-optimal or even mis-leading. In this paper, we propose a shift from the current mining-then-visualization paradigm, to jointly model these two core building blocks (i.e., mining and visualization) for brain network comparisons. The key idea is to integrate the human perception constraint into the mining block earlier so as to guide the analysis process. We formulate this as a multi-objective feature selection problem, and propose an integrated framework, BrainQuest, to solve it. We perform extensive empirical evaluations, both quantitatively and qualitatively, to demonstrate the effectiveness and efficiency of our approach.

Visually analyzing citation networks poses challenges to many fields of the data mining research. How can we summarize a large citation graph according to the user's interest? In particular, how can we illustrate the impact of a highly influential paper through the summarization? Can we maintain the sensory node-link graph structure while revealing the flow-based influence patterns and preserving a fine readability? The state-of-the-art influence maximization algorithms can detect the most influential node in a citation network, but fail to summarize a graph structure to account for its influence. On the other hand, existing graph summarization methods fold large graphs into clustered views, but can not reveal the hidden influence patterns underneath the citation network. In this paper, we first formally define the Influence Graph Summarization problem on citation networks. Second, we propose a matrix decomposition based algorithm pipeline to solve the IGS problem. Our method can not only highlight the flow-based influence patterns, but also easily extend to support the rich attribute information. A prototype system called VEGAS implementing this pipeline is also developed. Third, we present a theoretical analysis on our main algorithm, which is equivalent to the kernel k-mean clustering. It can be proved that the matrix decomposition based algorithm can approximate the objective of the proposed IGS problem. Last, we conduct comprehensive experiments with real-world citation networks to compare the proposed algorithm with classical graph summarization methods. Evaluation results demonstrate that our method significantly outperforms the previous ones in optimizing both the quantitative IGS objective and the quality of the visual summarizations.

Dynamic network visualization has been a challenging research topic due to the visual and computational complexity introduced by the extra time dimension. Existing solutions are usually good for overview and presentation tasks, but not for the interactive analysis of a large dynamic network. We introduce in this paper a new approach which considers only the dynamic network central to a focus node, also known as the egocentric dynamic network. Our major contribution is a novel 1.5D visualization design which greatly reduces the visual complexity of the dynamic network without sacrificing the topological and temporal context central to the focus node. In our design, the egocentric dynamic network is presented in a single static view, supporting rich analysis through user interactions on both time and network. We propose a general framework for the 1.5D visualization approach, including the data processing pipeline, the visualization algorithm design, and customized interaction methods. Finally, we demonstrate the effectiveness of our approach on egocentric dynamic network analysis tasks, through case studies and a controlled user experiment comparing with three baseline dynamic network visualization methods.

Aggregation is a scalable strategy for dealing with large network data. Existing network visualizations have allowed nodes to be aggregated based on node attributes or network topology, each of which has its own advantages. However, very few previous systems have the capability to enjoy the best of both worlds. This paper presents OnionGraph, an integrated framework for exploratory visual analysis of large heterogeneous networks. OnionGraph allows nodes to be aggregated based on either node attributes, topology, or a mixture of both. Subsets of nodes can be flexibly split and merged under the hierarchical focus+context interaction model, supporting sophisticated analysis of the network data. Node aggregations that contain subsets of nodes are displayed with multiple concentric circles, or the onion metaphor, indicating how many levels of abstraction they contain. We have evaluated the OnionGraph tool in two real-world cases. Performance experiments demonstrate that on a commodity desktop, OnionGraph can scale to million-node networks while preserving the interactivity for analysis.

Large-scale networks have become increasingly challenging to manage. It is vital for a system administrator or network manager to be able to analyze the vast amount of log data in order to detect suspicious behaviors or patterns, possibly due to malicious users/applications or faulty devices. While an intrusion detection system (IDS) log can provide a large number of warnings, exactly which alarms are true while the others are false, and more importantly what are the underlying causes are still difficult to know. To bridge the gap between network log and anomaly discovery, we design and implement a visualization tool that combines multiple commodity visualizations with minimum learning curve. While each individual view is well understood, the effects of such views in analyzing network anomalies are not well studied. Since each visualization technique has advantages as well as limitations in addressing a particular task, we show that these views, when combined and linked together, may provide an effective and lightweight network anomaly analysis tool. The web-based open platform may simplify network administration as well as promote collaborative analysis among researchers.

Detecting anomalous events from spatial data has important applications in real world. The spatial scan statistic methods are popular in this area. With maximizing the spatial statistical discrepancy by comparing observed data with a given baseline data distribution, significant spatial overdensity and underdensity can be detected. In reality, the spatial discrepancy is often irregularly shaped and has a structure of multiple spatial scales. However, a large-scale discrepancy pattern may not be significant when conducting fine granularity analysis. Meanwhile, local irregular boundaries of a maximized discrepancy cannot be well approximated with a coarse granularity analysis. Existing methods mostly work either on a fixed granularity, or with a regularly shaped scanning window. Thus, they have difficulties in characterizing such flexible spatial discrepancies. To solve the problem, in this paper we propose a novel discrepancy maximization algorithm, RefineScan. A grid hierarchy encoding multi-scale information is employed, making the algorithm capable of maximizing spatial discrepancies with multi-scale structures and irregular shapes. Experiments on a wide range of datasets demonstrate the advantages of RefineScan over the state-of-the-art algorithms: It always finds the largest discrepancy scores and remarkably better characterizes multi-scale discrepancy boundaries. Theoretical and empirical analyses also show that RefineScan has a moderate computational complexity and a good scalability.

Visually mining a large influence graph is appealing yet challenging. Existing summarization methods enhance the visualization with blocked views, but have adverse effect on the latent influence structure. How can we visually summarize a large graph to maximize influence flows? In particular, how can we illustrate the impact of an individual node through the summarization? Can we maintain the appealing graph metaphor while preserving both the overall influence pattern and fine readability? To answer these questions, we first formally define the influence graph summarization problem. Second, we propose an end-to-end framework to solve the new problem. Last, we report our experiment results. Evidences demonstrate that our framework can effectively approximate the proposed influence graph summarization objective while outperforming previous methods in a typical scenario of visually mining academic citation networks.

The visualization of complex network traffic involving a large number of communication devices is a common yet challenging task. Traditional layout methods create the network graph with overwhelming visual clutter, which hinders the network understanding and traffic analysis tasks. The existing graph simplification algorithms (e.g. community-based clustering) can effectively reduce the visual complexity, but lead to less meaningful traffic representations. In this paper, we introduce a new method to the traffic monitoring and anomaly analysis of large networks, namely Structural Equivalence Grouping (SEG). Based on the intrinsic nature of the computer network traffic, SEG condenses the graph by more than 20 times while preserving the critical connectivity information. Computationally, SEG has a linear time complexity and supports undirected, directed and weighted traffic graphs up to a million nodes. We have built a Network Security and Anomaly Visualization (NSAV) tool based on SEG and conducted case studies in several real-world scenarios to show the effectiveness of our technique.

In this paper we report on a case study of rumor transmission during a nationwide scandal via China's most popular microblogging service, weibo.com. Specifically, we explore dynamics of the rumor discourse by characterizing different statement types and their evolution over time. We examine the roles that different user groups play in the rumor discussions. Through qualitative and statistical analyses, our results identify seven reaction patterns to rumors and their different development trends. We reveal a three-stage pattern of the change of leadership during the rumor discussions. By connecting social theories on rumor transmission to the large scale social platform, this paper offers insight into understanding rumor development in social media, as well as utilizing microblogging data for effectively detecting, analyzing and controlling public rumors.

Traditional pattern mining methods usually work on single data sources. However, in practice, there are often multiple and heterogeneous information sources. They collectively provide contextual information not available in any single source alone describing the same set of objects, and are useful for discovering hidden contextual patterns. One important challenge is to provide a general methodology to mine contextual patterns easily and efficiently. In this paper, we propose a general framework to encode contextual information from multiple sources into a coherent representation---Contextual Information Graph (CIG). The complexity of the encoding scheme is linear in both time and space. More importantly, CIG can be handled by any single-source pattern mining algorithms that accept taxonomies without any modification. We demonstrate by three applications of the contextual association rule, sequence and graph mining, that contextual patterns providing rich and insightful knowledge can be easily discovered by the proposed framework. It enables Contextual Pattern Mining (CPM) by reusing single-source methods, and is easy to deploy and use in real-world systems.

Detecting significant overdensity or underdensity clusters in spatio-temporal data is critical for many real-world applications. Most existing approaches are designed to deal with regularly shaped clusters such as circular, elliptic and rectangular ones, but cannot work well on irregularly shaped clusters. In this paper, we propose GridScan, a grid-based approach for detecting irregularly shaped spatial clusters. In GridScan, a cluster is asymptotically described by a set of connected grid cells and is computed by a fast greedy region-growing algorithm with elaborating cluster merging in the process. The time complexity of GridScan is linear to the number of grids, making it scalable to very large datasets. A prospective spatio-temporal cluster detection approach, GridScan-Pro, is also proposed by extending GridScan. Experiments and a case study in the epidemic scenario demonstrate that our approaches greatly outperform existing ones in terms of accuracy, efficiency, and scalability.

Sentiment plays a critical role in many information-centric business scenarios. The opinion mining methods proposed in the recent decade have formed a solid foundation to investigate the sentiment analysis tasks, but are often too complicated and scattered to serve the needs of real customers. We introduce the VISA system in this paper, which applies the visualization technology to synthesize the sentiment analysis results and present to the end user in an interactive manner. VISA builds on the generic sentiment tuple based data model and consumes the different facets of sentiment data with coordinated multiple views, hence is scalable to work with most of existing sentiment analysis engines on various application domains. We showcase the usage of VISA in a real world example and demonstrate the system's effectiveness through the user trail in finding an appropriate hotel for his family trip.

Social network analysis (SNA) has been a research focus in multiple disciplines for decades, including sociology, healthcare, business management, etc. Traditional SNA researches concern more human and social science aspects—trying to undermine the real relationship of people and the impacts of these relationships. While online social networks have become popular in recent years, social media analysis, especially from the viewpoint of computer scientists, is usually limited to the aspects of people's behavior on specific websites and thus are considered not necessarily related to the day-to-day people's behavior and relationships. We conduct research to bridge the gap between social scientists and computer scientists by exploring the multifacet existing social networks in organizations that provide better insights on how people interact with each other in their professional life. We describe a comprehensive study on the challenges and solutions of mining and analyzing existing social networks in enterprise. Several aspects are considered, including system issues; privacy laws; the economic value of social networks; people's behavior modeling including channel, culture, and social inference; social network visualization in large-scale organization; and graph query and mining. The study is based on an SNA tool (SmallBlue) that was designed to overcome practical challenges and is based on the data collected in a global organization of more than 400 000 employees in more than 100 countries.

Multipath Switching systems (MPS) are intensely used in state-of-the-art core routers to provide terabit or even petabit switching capacity. One of the most intractable issues in designing MPS is how to load balance traffic across its multiple paths while not disturbing the intraflow packet orders. Previous packet-based solutions either suffer from delay penalties or lead to O(N^2 ) hardware complexity, hence do not scale. Flow-based hashing algorithms also perform badly due to the heavy-tailed flow-size distribution. In this paper, we develop a novel scheme, namely, Flow Slice (FS) that cuts off each flow into flow slices at every intraflow interval larger than a slicing threshold and balances the load on a finer granularity. Based on the studies of tens of real Internet traces, we show that setting a slicing threshold of 1-4 {\rm ms}, the FS scheme achieves comparative load-balancing performance to the optimal one. It also limits the probability of out-of-order packets to a negligible level (10^{ - 6}) on three popular MPSes at the cost of little hardware complexity and an internal speedup up to two. These results are proven by theoretical analyses and also validated through trace-driven prototype simulations.

The dynamic network visualization has been a challenging topic due to the complexity introduced by the extra time dimension. Existing solutions to this problem are usually good for the overview and presentation, but not for the interactive analysis. We propose in this paper a new approach which only considers the dynamic network central to a focus node (aka dynamic ego network). The navigation of the entire network is achieved by switching the focus node with user interactions. With this approach, the complexity of the compressed dynamic network is greatly reduced without sacrificing the network and time affinity central to the focus node. As a result, we are able to present each dynamic ego network in a single static view, well supporting user analysis on temporal network patterns. We describe our general framework including the network data pre-processing, 1.5D network and trend visualization design, layout algorithms, as well as several customized interactions. In addition, we show that our approach can also be extended to visualize the event-based and multimodal dynamic networks. Finally, we demonstrate, through two practical case studies, the effectiveness of our solution in support of visual evidence and pattern discovery.

Diagnosing a large-scale sensor network is a crucial but challenging task due to the spatiotemporally dynamic network behaviors of sensor nodes. In this demo, we present Sensor Anomaly Visualization Engine (SAVE), an integrated system that tackles the sensor network diagnosis problem using both visualization and anomaly detection analytics to guide the user quickly and accurately diagnose sensor network failures. Temporal expansion model, correlation graphs and dynamic projection views are proposed to effectively interpret the topological, correlational and dimensional sensor data dynamics and their anomalies. Through a real-world large-scale wireless sensor network deployment (GreenOrbs), we demonstrate that SAVE is able to help better locate the problem and further identify the root cause of major sensor network failures.

In this paper, we present a novel exploratory visual analytic system called TIARA (Text Insight via Automated Responsive Analytics), which combines text analytics and interactive visualization to help users explore and analyze large collections of text. Given a collection of documents, TIARA first uses topic analysis techniques to summarize the documents into a set of topics, each of which is represented by a set of keywords. In addition to extracting topics, TIARA derives time-sensitive keywords to depict the content evolution of each topic over time. To help users understand the topic-based summarization results, TIARA employs several interactive text visualization techniques to explain the summarization results and seamlessly link such results to the original text. We have applied TIARA to several real-world applications, including email summarization and patient record analysis. To measure the effectiveness of TIARA, we have conducted several experiments. Our experimental results and initial user feedback suggest that TIARA is effective in aiding users in their exploratory text analytic tasks.

The primary goal of the Midas project is to build a system that enables easy and scalable integration of unstructured and semi-structured information present across multiple data sources. As a first step in this direction, we have built a system that extracts and integrates information from regulatory filings submitted to the U.S. Securities and Exchange Commission (SEC) and the Federal Deposit Insurance Corporation (FDIC). Midas creates a repository of entities, events, and relationships by extracting, conceptualizing, integrating, and aggregating data from unstructured and semi-structured documents. This repository enables applications to use the extracted and integrated data in a variety of ways including mashups with other public data and complex risk analysis.

Visualizing large-scale online social network is a challenging yet essential task. This paper presents HiMap, a system that visualizes it by clustered graph via hierarchical grouping and summarization. HiMap employs a novel adaptive data loading technique to accurately control the visual density of each graph view, and along with the optimized layout algorithm and the two kinds of edge bundling methods, to effectively avoid the visual clutter commonly found in previous social network visualization tools. HiMap also provides an integrated suite of interactions to allow the users to easily navigate the social map with smooth and coherent view transitions to keep their momentum. Finally, we confirm the effectiveness of HiMap algorithms through graph-travesal based evaluations.

DNS amplification attacks utilize IP address spoofing and large numbers of open recursive DNS servers to perform the bandwidth consumption attack. During an attack, it ceaselessly fabricates DNS queries to the exploited open recursive DNS servers, and all the responses, often with larger size than the query messages, are reflected to the single victim due to the source IP address spoofing. While it is difficult to defend against this attack from the root causes by eliminating the open recursive DNS servers and IP spoofing for the whole Internet, in this paper, we take a different methodology to defend against it at the leaf router of victim's ISP or organization. We propose an efficient and low-cost hardware approach to first detect the DNS amplification attack accurately and responsively. Once the attack is confirmed, our approach is then activated to filter out all the illegitimate DNS responses by using a two-Bloom filter solution. We demonstrate that the memory cost of our approach is feasible for the hardware implementation even up to the OC-768 link. Through trace-driven simulations, it is shown that our approach is effective in both the detecting and filtering phases.

Efficiency and effectiveness are always the emphases of a scheduler, for both link and processor scheduling. Well-known scheduling algorithms such as surplus round robin (SRR) and elastic round robin (ERR) suffer from two fold shortcomings: 1) additional pre-processing queuing delay and post-processing resequencing delay are incurred due to the lack of short-term load-balancing; 2) bursty scheduling is caused due to blind preservation of scheduling history under non-backlogged traffic. In this paper, we propose a quantum-adaptive scheduling (QAS) algorithm, which: 1) synchronizes all the quanta in a fine-grained manner and, 2) adjusts the quanta intelligently based on processor utilization. We theoretically prove that the queuing fairness bound (QFB) for QAS is one third tighter than SRR and ERR. This result approaches the optimal value as obtained in shortest queue first (SQF) algorithm, while still maintaining O(1) complexity. Trace-driven simulations show that QAS reduces average packet delay by 18%~24% while cutting down the resequencing buffer size by more than 40% compared to SRR and ERR.

Multi-Path Switching systems (MPS) are intensively used in the state-of-the-art core routers. One of the most intractable issues is how to load-balance traffic across its multiple paths while not disturbing the intra-flow packet orders. In this paper, based on the studies of tens of real Internet traces, we develop a novel scheme, namely Flow-Slice (FS), which cuts off each flow into flow-slices at every intra-flow interval larger than a slicing threshold set to 1ms 4ms and balances the load on the finer granularity. Through theoretical analyses and comprehensive trace-driven simulations, we show that FS achieves impressive load-balancing performance with little hardware cost while limiting the packet out-of-order chances to a negligible level (below 10 -6).

Next-generation high-end network processors (NP) must address demands from both diversified applications and ever-increasing traffic pressure. One major challenge is to design an extraordinary scalable architecture. In this paper, it is argued that such an objective can only be sufficed by introducing highly paralleled structure, namely the paralleled processing-engine cluster (PPC). We demonstrate this point from the trade-off among aspects such as performance, programmability and flexibility. However, PPC natively suffers from several critical issues on load-balancing, intra-flow packet ordering and memory contention. After investigating several existing approaches, we present novel solutions for each issue according to the balance between performance and coast. Through intensive analysis and comprehensive simulations, it is shown that the shortest queue first scheduling with class-based prediction (SQF-C) performs nearly optimally, while the hardware based per-flow ordering mechanism resolves packet out-of-order independently with the load-balancing issue, inducting little throughput degradation. Implementing the unified solution, it is capable to design a PPC supporting up to OC-768c line rate. Real implementation is also carried out in our THNPU-1 prototype to verify the conclusions.

Flow-mapping parallel packet switch (FM-PPS) is the class of parallel packet switch adopting flow-level load-balancing algorithms. It dispatches packets of a micro-flow into an unchanged parallel switch, thus natively guarantees intra-flow packet orders. Due to the heavy tail of flow size distribution, it is concerned that FM-PPS may suffer from unpredictable performance which prevents it from real deployments. Motivated to clarify this issue, in this paper, we present an effective analytical model on FM-PPS and carry out intensive performance analysis. We find that under current Internet traffic patterns, both statistical packet delay and backlog bounds can be guaranteed if only several stability conditions are met. We further validate that a FM-PPS with OC-768c line rate is able to provide such guarantees under state-of-the-art RAM technology. A practical flow-mapping algorithm, namely constrained output round robin (CORR), is also proposed, which is designed to conform to these stability conditions, hence holds the delay and backlog bound.

Parallel Packet Switch (PPS) is used intensively in today's terabit router to construct the switching fabric. Basic PPS equally deals with all of the traffic in order to achieve uniform load-balancing and high throughput, but it fails to support differentiated QoS. With the recent blooming of delay- sensitive Internet traffic, such as the peer-to-peer live streaming and IPTV, differentiated QoS is becoming an urgent demand. In this paper, we propose a novel and practical framework, the Differentiated Service Parallel Packet Switch (DS-PPS), which supports three fundamental QoS features: guaranteed-delay (GD), guaranteed-bandwidth (GB) and best-effort (BE). By adaptively adjusting the number of switching planes offered to each QoS class, DS-PPS precisely controls the delay bounds of GD traffic and the drop precedence of GB traffic. We evaluate DS-PPS by extensive theoretical analyses and comprehensive simulations. Experimental results on a prototype implementation of the framework show that DS-PPS outperforms the basic PPS in three main aspects. First, the average delay of TCP short packet under full load is reduced by more than 94%. Second, the average delay of real-time traffic under full load is reduced by more than 82%. And third, the GB traffic of low drop precedence is guaranteed of nearly three times the throughput of high drop precedence at the hotspots. Significantly, our proposed DS-PPS framework is universal and scalable to support various kinds of emerging QoS-sensitive applications in multi-service terabit routers without any extra overhead.