Graph anomaly detection aims to identify anomalous occurrences in networks. However, this is more challenging than the traditional anomaly detection problem because anomalies in graphs can manifest ...in three different forms: anomalous nodes, anomalous edges, and anomalous sub-graphs. It is crucial to detect all these anomaly types within a single framework to provide a unified solution to the graph anomaly detection task. The main objective of this study is to propose a model that is capable of detecting all static graph anomalies in a single architecture across various domains. In this paper, we introduce DeGAN (Decomposition-based unified Graph ANomaly detection), a novel framework for unified graph anomaly detection in static networks. DeGAN combines two deep learning concepts with graph decomposition to identify anomalous graph objects: a graph neural network and an adversarial autoencoder. DeGAN is featured with its capability to detect anomalies in a single process, and adopting graph decomposition has improved performance compared to the traditional adversarial learning approach. DeGAN is evaluated with six real-world datasets to demonstrate that our framework can work in multiple domains. Experimental results demonstrate that DeGAN is capable of detecting anomalous nodes, edges, and sub-graphs within a single model. Additionally, the effectiveness of the sub-components of DeGAN has been demonstrated through experimentation. Even though DeGAN is proposed for plain graphs, it can be extended to attributed and dynamic graphs.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Let G ( V , E ) be a digraph (directed graph) with n nodes and e arcs. Digraph G* = ( V , E* ) is the reflexive, transitive closure if v → u ∈ E* iff there is a path from v to u in G . Efficient ...storage of G* is important for supporting reachability queries which are not only common in graph databases, but also serve as fundamental operations used in many graph algorithms. A lot of strategies have been proposed based on the graph labeling, by which each node is assigned with certain labels such that the reachability of any two nodes through a path can be determined by their labels. Among them are interval labeling, chain decomposition, 2-hop labeling, and path-trees, as well as partial index based methods. However, due to the very large size of many real world graphs, the computational cost and size of labels using existing methods would prove too expensive to be practical. In this paper, we propose a new approach to deduct and decompose a graph into a series of spanning trees and transform a query q to a series of subqueries each evaluated against a spanning tree. Using the so-called tree labeling, each subquery needs only O(1) time. More importantly, the number of such subqueries is <inline-formula><tex-math notation="LaTeX">\ll</tex-math> <mml:math><mml:mo>≪</mml:mo></mml:math><inline-graphic xlink:href="chen-ieq1-3220191.gif"/> </inline-formula> n . Thus, q can be evaluated very efficiently. We demonstrate both analytically and empirically the efficiency and effectiveness of our method. While the query time of our method is orders of magnitude better than almost all the existing strategies, its indexing time and index sizes are comparable to them.
The biclique partition number of a graph G=(V,E), denoted bp(G), is the minimum number of pairwise edge disjoint complete bipartite subgraphs of G so that each edge of G belongs to exactly one of ...them. It is easy to see that bp(G)≤n−α(G), where α(G) is the maximum size of an independent set of G. Erdős conjectured in the 80's that for almost every graph G equality holds; i.e., if G=Gn,1/2 then bp(G)=n−α(G) with high probability. Alon showed that this is false. We show that the conjecture of Erdős is true if we instead take G=Gn,p, where p is constant and less than a certain threshold value p0≈0.312. This verifies a conjecture of Chung and Peng for these values of p. We also show that if p0<p<1/2 then bp(Gn,p)=n−(1+Θ(1))α(Gn,p) with high probability.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
In this article, we investigate the UAV-aided edge caching to assist terrestrial vehicular networks in delivering high-bandwidth content files. Aiming at maximizing the overall network throughput, we ...formulate a joint caching and trajectory optimization (JCTO) problem to make decisions on content placement, content delivery, and UAV trajectory simultaneously. As the decisions interact with each other and the UAV energy is limited, the formulated JCTO problem is intractable directly and timely. To this end, we propose a deep supervised learning scheme to enable intelligent edge for real-time decision-making in the highly dynamic vehicular networks. In specific, we first propose a clustering-based two-layered (CBTL) algorithm to solve the JCTO problem offline. With a given content placement strategy, we devise a time-based graph decomposition method to jointly optimize the content delivery and trajectory design, with which we then leverage the particle swarm optimization (PSO) algorithm to further optimize the content placement. We then design a deep supervised learning architecture of the convolutional neural network (CNN) to make fast decisions online. The network density and content request distribution with spatio-temporal dimensions are labeled as channeled images and input to the CNN-based model, and the results achieved by the CBTL algorithm are labeled as model outputs. With the CNN-based model, a function which maps the input network information to the output decision can be intelligently learnt to make timely inference and facilitate online decisions. We conduct extensive trace-driven experiments, and our results demonstrate both the efficiency of CBTL in solving the JCTO problem and the superior learning performance with the CNN-based model.
In this paper, we present a deep learning-based approach, namely a dual CNN–RNN for multiple people tracking. We follow tracking-by-detection paradigm by first training a CNN to measure the ...similarity of two detection boxes. To solve the data association (DA) problem, we build a graph with nodes as detections and edge costs that are the outputs of a CNN. The general minimum cost lifted multi-cut problem (LMP) and corresponding optimization algorithms are utilized to solve the DA problem. To tackle occlusion and ID-switch problems, an RNN network is proposed to predict the nonlinear motion of people. Moreover, we utilize target motion information to stitch tracklets and build long trajectories. The results of our experiments conducted on Multiple Object Tracking Benchmark 2016 (MOT2016) confirm the efficiency of the proposed algorithm.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
A G -decomposition of the complete graph Kn is a family of pairwise edge disjoint subgraphs of Kn , all isomorphic to G , such that every edge of Kn belongs to exactly one copy of G . Using standard ...decomposition techniques based on ρ -labelings, introduced by Rosa in 1967, and their modifications we show that each of the ten non-isomorphic connected unicyclic graphs with eight edges containing the pentagon decomposes the complete graph Kn whenever the necessary conditions are satisfied.
We consider a concept related with decompositions of graphs to locally irregular subgraphs and the notion of almost irregular subgraphs, introduced recently by Alon and Wei. We say that a graph is ...locally almost irregular if its every vertex has at most one neighbour with the same degree as itself. We conjecture that any graph can be edge decomposed to two locally almost irregular subgraphs, and we prove a relaxation of this supposition, where we admit for every vertex v more than one, yet finitely bounded number of neighbours with the same degree as v. In particular we show it suffices to allow 7 such neighbours in the case of regular graph, and no more than 48 in general.
•Every regular graph is decomposable to 2 locally 7-defective irregular subgraphs.•Every graph is decomposable to 2 locally 48-defective irregular subgraphs.•For d≥464, a random regular graph G(n,d) is a.a.s. decomposable to 2 locally irregular subgraphs.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
For some k∈Z≥0∪{∞}, we call a linear forest k-bounded if each of its components has at most k edges. We will say a (k,ℓ)-bounded linear forest decomposition of a graph G is a partition of E(G) into ...the edge sets of two linear forests Fk,Fℓ where Fk is k-bounded and Fℓ is ℓ-bounded. We show that the problem of deciding whether a given graph has such a decomposition is NP-complete if both k and ℓ are at least 2, NP-complete if k≥9 and ℓ=1, and is in P for (k,ℓ)=(2,1). Before this, the only known NP-complete cases were the (2,2) and (3,3) cases. Our hardness result answers a question of Bermond et al. from 1984. We also show that planar graphs of girth at least nine decompose into a linear forest and a matching, which in particular is stronger than 3-edge-coloring such graphs.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Finding k-edge connected components (k-ECCs) is widely used to investigate the major cohesive structures within a graph. Traditional methods utilizing global minimum cut to split the graph ...iteratively are too slow to deal with graphs of a large size. Recently, approximate algorithms based on a decomposition framework have been proposed to speed up the process. However, these algorithms produce low-quality results in graphs containing vertex pairs that are k-connected but do not belong to a k-ECC. In this paper, we propose a decomposition framework that utilizes a local edge connectivity check method to obtain high-quality results in a shorter period. The proposed method utilizes an improved maximum flow algorithm to detect k-ECCs from local k-cores by merging more vertices in each iteration than existing methods. Moreover, a pruning strategy is applied in the decomposition framework to reduce unnecessary branches in the decomposition tree. Our experimental results on both synthetic and real graphs show that our proposed algorithm is faster than the state-of-the-art algorithms in most datasets and achieves effective results among the approximate algorithms with a 96% accuracy on our experimental datasets.
•An efficient local edge connectivity check based decomposition framework to detect k-ECCs with high accuracy of results.•A k-core based maximal merging and a pruning strategy for optimizing the algorithm processing time and the height of decomposition tree.•An improved augmenting path flow method to directly calculate the minimum cut of two vertices in the check procedure.•Experimental results show that the algorithm can detect k-ECCs with outstanding speed while producing high-quality results (96% accuracy).
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
PDF
