How does the graph change if we summarize it by merging nodes? How can we summarize the graph while preserving its spectral characteristics? Graph summarization aims to present a graph in a compact summary graph form while keeping its important structural information. Existing methods primarily focus on preserving the adjacency matrix. In contrast, spectral graph theory provides a powerful tool to describe the characteristics of a graph. In this paper, we propose a novel graph summarization method that preserves the spectral characteristics, including spectral moments and heat traces. We analyze the change of the spectral characteristics after summarization and design a simple yet effective summarization method based on agglomerative clustering. Our approach is extensively evaluated on real-world datasets. The experimental results show that our method excels in preserving the spectral characteristics and obtains better performance on the subsequent graph classification task.

Graph summarization is a useful tool for analyzing large-scale graphs. Some works tried to preserve original node embeddings encoding rich structural information of nodes on the summary graph. However, their algorithms are designed heuristically and not theoretically guaranteed. In this article, we theoretically study the problem of preserving node embeddings on summary graph. We prove that three matrix-factorization-based node embedding methods of the original graph can be approximated by that of the summary graph, and we propose a novel graph summarization method, named HCSumm , based on this analysis. Extensive experiments are performed on real-world datasets to evaluate the effectiveness of our proposed method. The experimental results show that our method outperforms the state-of-the-art methods in preserving node embeddings.

How can we effectively detect fake reviews or fraudulent links on a website? How can we spot communities that suddenly appear based on users’ interactions? And how can we efficiently find the minimum cut in a large graph? All of these are related to the finding of dense subgraphs, a significant primitive problem in graph analysis with extensive applications across various domains. In this paper, we focus on formulating the problem of the densest subgraph detection and theoretically compare and contrast several correlated problems. Moreover, we propose a unified framework,GenDS, for the densest subgraph detection, provide some theoretical analysis based on the network flow and spectral graph theory, and devise simple and computationally efficient algorithms,SpecGDSandGepGDS, to solve it by leveraging the spectral properties and greedy search. We conduct thorough experiments on 40 real-world networks with up to 1.47 billion edges from various domains. We demonstrate that ourSpecGDSyields up to$58.6 \ \times$speedup and achieves better or approximately equal-quality solutions for the densest subgraph detection compared to the baselines.GepGDSalso reveals some properties of generalized eigenvalue problems for theGenDS. Also, our methods scale linearly with the graph size and are proven effective in applications such as finding collaborations that appear suddenly in an extensive, time-evolving co-authorship network.

Given a heterogeneous multilayer network with various connections in pharmacology, how can we detect components with intensive interactions and strong dependencies? Can we accurately capture suspicious groups in a multi-lot transaction network under camouflage? These challenges related to dense subgraph detection have been extensively studied in simple graphs (such as bipartite graph, multi-view network) but remain under-explored on complex networks. Existing methods struggle to effectively handle theintricate dependencies, let alone accurately identify theinterrelated dense connected patternswithin a series of complex heterogeneous networks. In this paper, we proposeInDuen, a novel algorithm designed to detect interrelated densest subgraphs in multilayer networks through joint optimization of coupled factorization and local search for an elaborate-designed joint density measure. It is(a)effective for both large synthetic and real networks,(b)resistant to camouflage for anomaly detection, and(c)linearly scalable. Experimental results demonstrate thatInDuenoutperforms the state-of-the-art baselines in accurately detecting interrelated densest subgraphs under various settings. Furthermore,InDuenuncovers some intriguing patterns in real-world data, i.e., closely cooperated academic groups and interrelated dependent functional components in biology-net.InDuenachieves more than$35 \times$speedup compared to the SOTA methodDestine.

Dense subtensor detection gains remarkable success in spotting anomalies and fraudulent behaviors for multi-aspect data (i.e., tensors), like in social media and event streams. Existing methods detect the densest subtensors flatly and separately, with the underlying assumption that those subtensors are exclusive. However, many real-world tensors usually present hierarchical properties, e.g., the core-periphery structure and dynamic communities in networks. It is also unexplored how to fuse the prior knowledge into dense pattern detection to capture the local behavior. In this article, we propose CatchCore , a novel framework to efficiently find the hierarchical dense subtensors. We first design a unified metric for dense subtensor detection, which can be optimized with gradient-based methods. With the proposed metric, CatchCore detects hierarchical dense subtensors through the hierarchy-wise alternative optimization and finds local dense patterns concerning some items in a query manner. Finally, we utilize the minimum description length principle to measure the quality of detection results and select the optimal hierarchical dense subtensors. Extensive experiments on synthetic and real-world datasets demonstrate that CatchCore outperforms the top competitors in accuracy for detecting dense subtensors and anomaly patterns, like network attacks. Additionally, CatchCore successfully identifies a hierarchical researcher co-authorship group with intense interactions in the DBLP dataset; it can also capture core collaboration and multi-hop relations around some query objects. Meanwhile, CatchCore also scales linearly with all aspects of tensors.

Time series data naturally exist in many domains including medical data analysis, infrastructure sensor monitoring, and motion tracking. However, a very small portion of anomalous time series can be observed, comparing to the whole data. Most existing approaches are based on the supervised classification model requiring representative labels for anomaly class(es), which is challenging in real-world problems. So can we learn how to detect anomalous time ticks in an effective yet efficient way, given mostly normal time series data? Therefore, we propose an unsupervised reconstruction model named BeatGAN which learns to detect anomalies based on normal data, or data which majority of samples are normal. BeatGAN provides a framework to adversarially learn to reconstruct, which can cooperate with both 1-d CNN and RNN. Rarely observed anomalies can result in larger reconstruction errors, which are then detected based on extreme value theory. Moreover, data augmentation with dynamic time warping regularizes reconstruction and provides robustness. In the experiments, effectiveness and sensitivity are studied in both synthetic data and various real-world time series. BeatGAN achieves better accuracy and fast inference.

Given a stream of money transactions between accounts in a bank, how can we accurately detect money laundering agent accounts and suspected behaviors in real-time? Money laundering agents try to hide the origin of illegally obtained money by dispersive multiple small transactions and evade detection by smart strategies. Therefore, it is challenging to accurately catch such fraudsters in an unsupervised manner. Existing approaches do not consider the characteristics of those agent accounts and are not suitable to the streaming settings. Therefore, we propose MonLAD and MonLAD-W to detect money laundering agent accounts in a transaction stream by keeping track of their residuals and other features; we devise AnoScore algorithm to find anomalies based on the robust measure of statistical deviation. Experimental results show that MonLAD outperforms the state-of-the-art baselines on real-world data and finds various suspicious behavior patterns of money laundering. Additionally, several detected suspected accounts have been manually-verified as agents in real money laundering scenario.

Given a large graph, how can we summarize it with fewer nodes and edges while maintaining its key properties, e.g.node degrees and graph spectrum?As a solution, graph summarization, which aims to find the compact representation for optimally describing and reconstructing a given graph, has received much attention, and numerous methods have been developed for it.However, many existing methods adopt the uniform reconstruction scheme, which is an unrealistic assumption as most real-world graphs have highly skewed node degrees, even within communities.Therefore we propose a degree-preserving graph summarization model, DPGS, with a novel reconstruction scheme based on the configuration model.To optimize the Minimum Description Length of our model, we deisgn a linearly scalable algorithm using hashing techniques.We theoretically show that the minimized reconstruction error bounds the perturbation of graph spectral information.Extensive experiments on realworld datasets show that DPGS yields more accurate summary graphs than several well-known baselines.Moreover, our reduced summary graphs can effectively train graph neural networks (GNNs) while saving computational cost.

Graph Convolutional Networks (GCNs) have achieved state-of-the-art performance on node classification. However, recent works have shown that GCNs are vulnerable to adversarial attacks, such as additions or deletions of adversarially-chosen edges in the graph, in order to mislead the node classification algorithms. How can we design robust GCNs that are resistant to such adversarial attacks? More challengingly, how can we do this in a way that is provably robust? We propose a robust node classification approach based on a low-pass `message passing' mechanism, that (a) reduces the effectiveness of adversarial attacks in experiments, and (b) provides theoretical guarantees against adversarial attacks. Our approach can be embedded into the existing GCN architectures to enhance their robustness. Empirical results show that our loss-pass method effectively improves the performance of multiple GCNs under miscellaneous perturbations and helps them to achieve superior performance on various graphs.

How can one quickly answer the most and top popular objects at any time, given a large log stream in a system of billions of users? It is equivalent to find the mode and top-frequent elements in a dynamic array corresponding to the log stream. However, most existing work either restrain the dynamic array within a sliding window, or do not take advantages of only one element can be added or removed in a log stream. Therefore, we propose a profiling algorithm, named S-Profile, which is of $O(1)$ time complexity for every updating of the dynamic array, and optimal in terms of computational complexity. With the profiling results, answering the queries on the statistics of dynamic array becomes trivial and fast. With the experiments of various settings of dynamic arrays, our accurate S-Profile algorithm outperforms the well-known methods, showing at least 2X speedup to the heap based approach and 13X or larger speedup to the balanced tree based approach.

Consider a stream of time-stamped events, such as taxi rides, where we record the start and end locations of each ride. How do we learn a matrix factorization model which takes into account seasonal patterns (such as: rides toward office areas occur more frequently in the morning), and use it to forecast taxi rides tomorrow? Also, how can we model drift (such as population growth), and detect sudden changes (or anomalies)? Existing matrix factorization algorithms do not take seasonal patterns into account. We propose SMF (Seasonal Matrix Factorization), a matrix factorization model for seasonal data, and a streaming algorithm for fitting it. SMF is (a) accurate in forecasting: outperforming baselines by 13% to 60% in RMSE; (b) online: requiring fixed memory even as more data is received over time, and scaling linearly; (c) effective: providing interpretable results. In addition, we propose SMF-A, an algorithm which detects anomalies in a computationally feasible way, without forecasting every observation in the matrix.

How to quantify influences between users, seeing that social network users influence each other in their temporal behaviors? Previous work has directly defined an independent model parameter to capture the interpersonal influence between each pair of users. To do so, these models need a parameter for each pair of users, which results in high-dimensional models becoming easily trapped into the overfitting problem. However, such models do not consider how influences depend on each other if influences are sent from the same user or if influences are received by the same user. Therefore, we propose a model that defines parameters for every user with a latent influence vector and a susceptibility vector, opposite to define influences on user pairs. Such low-dimensional representations naturally cause the interpersonal influences involving the same user to be coupled with each other, thus reducing the model’s complexity. Additionally, the model can easily consider the temporal information and sentimental polarities of users’ messages. Finally, we conduct extensive experiments on two real-world Microblog datasets, showing that our model with such representations achieves best performance on three prediction tasks, compared to the state-of-the-art and pair-wise baselines.

How can we detect fraud in a big graph with rich properties, as online fraudsters invest more resources, including purchasing large pools of fake user accounts and dedicated IPs, to hide their fraudulent attacks? To achieve robustness, existing approaches detected dense sub-graphs as suspicious patterns in an unsupervised way, such as average degree maximization. However, such approaches suffer from the bias of including more nodes than necessary, resulting in lower accuracy and increased need for manual verification. Therefore, we propose HoloScope, which introduces a novel metric “contrast suspiciousness” integrating information from graph topology and spikes to more accurately detect fraudulent users and objects. Contrast suspiciousness dynamically emphasizes the contrasting patterns between fraudsters and normal users, making HoloScope capable of distinguishing the synchronized and strange behaviors of fraudsters by means of topology, bursts and drops, and rating scores. In addition, we provide theoretical bounds for how much this method increases the time cost needed for fraudsters to conduct adversarial attacks. Moreover, HoloScope has a concise framework and sub-quadratic time complexity, making the algorithm reproducible and scalable. In extensive experiments, HoloScope achieved significant accuracy improvements on real data with injected labels and true labels, when compared with state-of-the-art fraud detection methods.

As online fraudsters invest more resources, including purchasing large pools of fake user accounts and dedicated IPs, fraudulent attacks become less obvious and their detection becomes increasingly challenging. Existing approaches such as average degree maximization suffer from the bias of including more nodes than necessary, resulting in lower accuracy and increased need for manual verification. Hence, we propose HoloScope, which introduces a novel metric "contrast suspiciousness" integrating information from graph topology and spikes to more accurately detect fraudulent users and objects. Contrast suspiciousness dynamically emphasizes the contrast patterns between fraudsters and normal users, making HoloScope capable of distinguishing the synchronized and anomalous behaviors of fraudsters on topology, bursts and drops, and rating scores. In addition, we provide theoretical bounds for how much this increases the time cost needed for fraudsters to conduct adversarial attacks. Moreover, HoloScope has a concise framework and sub-quadratic time complexity, making the algorithm reproducible and scalable. Extensive experiments showed that HoloScope achieved significant accuracy improvements on synthetic and real data, compared with state-of-the-art fraud detection methods.

Sentiment classification is a topic-sensitive task, i.e., a classifier trained from one topic will perform worse on another. This is especially a problem for the tweets sentiment analysis. Since the topics in Twitter are very diverse, it is impossible to train a universal classifier for all topics. Moreover, compared to product review, Twitter lacks data labeling and a rating mechanism to acquire sentiment labels. The extremely sparse text of tweets also brings down the performance of a sentiment classifier. In this paper, we propose a semi-supervised topic-adaptive sentiment classification (TASC) model, which starts with a classifier built on common features and mixed labeled data from various topics. It minimizes the hinge loss to adapt to unlabeled data and features including topic-related sentiment words, authors' sentiments and sentiment connections derived from“@” mentions of tweets, named as topic-adaptive features. Text and non-text features are extracted and naturally split into two views for co-training. The TASC learning algorithm updates topic-adaptive features based on the collaborative selection of unlabeled data, which in turn helps to select more reliable tweets to boost the performance. We also design the adapting model along a timeline (TASC-t) for dynamic tweets. An experiment on 6 topics from published tweet corpuses demonstrates that TASC outperforms other well-known supervised and ensemble classifiers. It also beats those semi-supervised learning methods without feature adaption. Meanwhile, TASC-t can also achieve impressive accuracy and F-score. Finally, with timeline visualization of “river” graph, people can intuitively grasp the ups and downs of sentiments' evolvement, and the intensity by color gradation.

Sentiment classification is an important problem in tweets mining. There lack labeled data and rating mechanism for generating them in Twitter service. And topics in Twitter are more diverse while sentiment classifiers always dedicate themselves to a specific domain or topic. Thus it is a challenge to make sentiment classification adaptive to diverse topics without sufficient labeled data. Therefore we formally propose an adaptive multiclass SVM model which transfers an initial common sentiment classifier to a topic-adaptive one. To tackle the tweet sparsity, non-text features are explored besides the conventional text features, which are intuitively split into two views. An iterative algorithm is proposed for solving this model by alternating among three steps: optimization, unlabeled data selection and adaptive feature expansion steps. The algorithm alternatively minimizes the margins of two independent objectives on different views to learn coefficient matrices, which are collaboratively used for unlabeled tweets selection from the topic that the algorithm is adapting to. And then topic-adaptive sentiment words are expended based on the above selection, in turn to help the first two steps find more confident and unlabeled tweets and boost the final performance. Comparing with the well-known supervised sentiment classifiers and semi-supervised approaches, our algorithm achieves promising increases in accuracy averagely on the 6 topics from public tweet corpus.

Nowadays, short texts are very prevalent in various web applications, such as microblogs, instant messages. The severe sparsity of short texts hinders existing topic models to learn reliable topics. In this paper, we propose a novel way to tackle this problem. The key idea is to learn topics by exploring term correlation data, rather than the high-dimensional and sparse term occurrence information in documents. Such term correlation data is less sparse and more stable with the increase of the collection size, and can well capture the necessary information for topic learning. To obtain reliable topics from term correlation data, we first introduce a novel way to compute term correlation in short texts by representing each term with its co-occurred terms. Then we formulated the topic learning problem as symmetric non-negative matrix factorization on the term correlation matrix. After learning the topics, we can easily infer the topics of documents. Experimental results on three data sets show that our method provides substantially better performance than the baseline methods.

Social tagging has grown in popularity on the web due to its effectiveness in organizing and accessing web pages. This short paper addresses the problem of automated social tagging, which aims to predict tags for web pages automatically and help with future navigation, filtering or search. We explore and find three foundations of the collaborative tags in social tagging services, that are consistency, sharability and stability. The complementary advantages are studied among three well-known methods, i.e. TF-weighted keyword extraction, collaborative filtering approach, and Corr-LDA (correspondence latent Dirichlet allocation) topic model. We then propose a blending model for automated social tagging to emphasize all the foundations, which linearly combines those tags generated by the three methods, and a permutation probability model is built to learn the linear blending. With the experiments on 50,000 training and 10,000 testing web pages from Delicious database, the results show that our blending method outperforms the four baselines. Furthermore, compared with both topic models, Corr-LDA and mixed membership LDA, our approach results in 14.2% and 25.6% of NDCG10improvement separately.

Non-negative matrix factorization (NMF) has been successfully applied in document clustering. However, experiments on short texts, such as microblogs, Q&A documents and news titles, suggest unsatisfactory performance of NMF. An major reason is that the traditional term weighting schemes, like binary weight and tfidf, cannot well capture the terms' discriminative power and importance in short texts, due to the sparsity of data. To tackle this problem, we proposed a novel term weighting scheme for NMF, derived from the Normalized Cut (Ncut) problem on the term affinity graph. Different from idf, which emphasizes discriminability on document level, the Ncut weighting measures terms' discriminability on term level. Experiments on two data sets show our weighting scheme significantly boosts NMF's performance on short text clustering.