We investigate the computational complexity of the following restricted variant of SUBgraph ISOMORPHISM: given a pair of connected graphs G = (V-G, E-G) and H = (V-H, E-H), determine if H is isomorphic to a spanning s...
详细信息
We investigate the computational complexity of the following restricted variant of SUBgraph ISOMORPHISM: given a pair of connected graphs G = (V-G, E-G) and H = (V-H, E-H), determine if H is isomorphic to a spanning subgraph of G. The problem is NP-complete in general, and thus we consider cases where G and H belong to the same graph class such as the class of proper interval graphs, of trivially perfect graphs, and of bipartite permutation graphs. For these graph classes, several restricted versions of SUBgraph ISOMORPHISM such as HAMILTONIAN PATH, CLIQUE, BANDWIDTH, and graph ISOMORPHISM can be solved in polynomial time, while these problems are hard in general. (c) 2012 Elsevier B.V. All rights reserved.
Two vertices of an undirected graph are called k-edge-connected if there exist k edge-disjoint paths between them (equivalently, they cannot be disconnected by the removal of less than k edges from the graph). Equival...
详细信息
Two vertices of an undirected graph are called k-edge-connected if there exist k edge-disjoint paths between them (equivalently, they cannot be disconnected by the removal of less than k edges from the graph). Equivalence classes of this relation are called classes of k-edge-connectivity or k-edge-connected components. This paper describes graph structures relevant to classes of 4-edge-connectivity and traces their transformations as new edges are inserted into the graph. Data structures and an algorithm to maintain these classes incrementally are given. Starting with the empty graph, any sequence of q Same-4-Class? queries and it Insert-Vertex and lit Insert-Edge updates can be performed in O(q + m + ii log n total time. Each individual query requires O(1) time in the worst-case. In addition, an algorithm for maintaining the classes of k-edge-connectivity (k arbitrary) in a (k-1)-edge-connected graph is presented. Its complexity is O(q + m + n). with O(M + k(2)n log(n/k)) preprocessing, where M is the number of edges initially in the graph and n is the number of its vertices.
The model-checking problem for monadic second-order logic on graphs is fixed-parameter tractable with respect to tree-width and clique-width. The proof constructs finite automata from monadic second-order sentences. T...
详细信息
The model-checking problem for monadic second-order logic on graphs is fixed-parameter tractable with respect to tree-width and clique-width. The proof constructs finite automata from monadic second-order sentences. These automata recognize the terms over fixed finite signatures that define graphs satisfying the given sentences. However, this construction produces automata of hyper-exponential sizes, and is thus impossible to use in practice in many cases. To overcome this difficulty, we propose to specify the transitions of automata by programs instead of tables. Such automata are called fly-automata. By using them, we can check certain monadic second-order graph properties with limited quantifier alternation depth, that are nevertheless interesting for graph Theory. We give explicit constructions of automata relative to graphs of bounded clique-width, and we report on experiments. (C) 2012 Elsevier B.V. All rights reserved.
We propose a novel recommendation algorithm based on acyclic paths in an edge-colored graph. In our method, all the objects including users, items to recommend, and other things usable to recommendation are represente...
详细信息
ISBN:
(纸本)9783030975463;9783030975456
We propose a novel recommendation algorithm based on acyclic paths in an edge-colored graph. In our method, all the objects including users, items to recommend, and other things usable to recommendation are represented as vertices in an edge-colored directed graph, in which edge color represents relation between the objects of its both ends. By setting each edge weight appropriately so as to reflect how much the object corresponding to its one end is preferred by people who prefer the object corresponding to its other end, the probability of an s-t path, which is defined as the product of its component edges' weights, can be regarded as preference degree of item t (item corresponding to vertex t) by user s (user corresponding to vertex s) in the context represented by the path. Given probability threshold theta, the proposed algorithm recommends user s to item t that has high sum of the probabilities of all the acyclic s-t paths whose probability is at least theta. For item t recommended to user s, the algorithm also shows high probability color sequences of those s-t paths, from which we can know main contexts of the recommendation of item t for user s. According to our experiments using real-world datasets, the recommendation performance of our method is comparable to the non-explainable state-of-the-art recommendation methods.
graph analytics are arguably one of the most demanding workloads for high-performance systems and interconnection networks. graph applications often display all-to-all, fine-grained, high-rate communication patterns t...
详细信息
ISBN:
(纸本)9781450337236
graph analytics are arguably one of the most demanding workloads for high-performance systems and interconnection networks. graph applications often display all-to-all, fine-grained, high-rate communication patterns that expose the limits of the network protocol stacks. Load and communication imbalance generate hard-to-predict network hot-spots, and may require computational steering due to unpredictable data distributions. In this paper we present a lightweight communication library, implemented "on the metal" of BlueGene/Q and POWER7 IH that we have used to support large-scale graph algorithms up to 96K processing nodes and 6 million threads. With this library we have explored several optimization techniques, including overlapped communication, non-blocking collectives, message aggregation, and computation in the network for special collective communication patterns, such as parallel prefix. The experimental results show significant performance improvements, ranging from 5X to 10X, when compared to equally optimized MPI implementations.
Structural graph clustering (SCAN) is a popular clustering technique. Using the concept of is an element of-neighborhood, SCAN defines the core vertices that uniquely determine the clusters of a graph. Most existing s...
详细信息
ISBN:
(数字)9781665408837
ISBN:
(纸本)9781665408837
Structural graph clustering (SCAN) is a popular clustering technique. Using the concept of is an element of-neighborhood, SCAN defines the core vertices that uniquely determine the clusters of a graph. Most existing studies assume that the graph processed by SCAN contains no controlled edges. Few studies, however, have focused on manipulating SCAN by injecting edges. Manipulation of SCAN can be used to assess its robustness and lay the groundwork for developing robust clustering algorithms. To fill this gap and considering the importance of the is an element of-neighborhood for SCAN, we propose a problem, denoted as MN, for manipulating SCAN. The MN problem aims to maximize the is an element of-neighborhood of the target vertex by inserting some edges. On the theoretical side, we prove that the MN problem is both NP-hard and APX-hard, and also is non-submodular and non-monotonic. On the algorithmic side, we design an algorithm by focusing on how to select vertices to join is an element of neighborhood and thus avoid enumerating edges to report a solution. As a result, our algorithm bypasses the non-monotonicity nature of the MN problem. Extensive experiments on real-world graphs show that our algorithm can effectively solve the proposed MN problem.
graph structures have shown to represent a viable approach to developingAGI. This paper describes howa knowledge graph could be represented in neurons and introduces theUniversal Knowledge Store (UKS), an open-source ...
详细信息
graph structures have shown to represent a viable approach to developingAGI. This paper describes howa knowledge graph could be represented in neurons and introduces theUniversal Knowledge Store (UKS), an open-source implementation, which could form one component of AGI. Unlike backpropagationrelated systems which have only the most tenuous biological relationship, graph structures can be built from basic biological neuron models.
With the increase of large graph data arising in applications like Web, social network, knowledge graph, and so on, there is a growing need for partitioning and repartitioning large graph data in graph data systems. H...
详细信息
ISBN:
(纸本)9783030594152;9783030594169
With the increase of large graph data arising in applications like Web, social network, knowledge graph, and so on, there is a growing need for partitioning and repartitioning large graph data in graph data systems. However, the existing graph repartitioning methods are known for poor efficiency in the dynamic environment. In this paper, we devise an efficient lightweight method to identify and move the candidate vertices to achieve graph repartitioning in the dynamic environment. Different from previous approaches that just focus on the case of moving a single vertex as a basic unit, we show that the movement of some closely connected vertices as a group can further improve the quality of graph repartitioning result. We conduct experiments on a large set of real and synthetic graph data sets, and the results showed that the proposed method is more efficient comparing with existing method in several aspects.
k-nearest neighbor (kNN) search is a fundamental problem in graph mining. This search finds the k most relevant nodes to a given query node. The increased use of social network services and map applications due to the...
详细信息
ISBN:
(纸本)9783031683084;9783031683091
k-nearest neighbor (kNN) search is a fundamental problem in graph mining. This search finds the k most relevant nodes to a given query node. The increased use of social network services and map applications due to the proliferation of mobile devices has necessitated faster searches. Although pre-constructing an index using graphs can accelerate a kNN search, existing methods struggle handling dynamic graph updates. Herein we propose an efficient index update method for dynamic graphs that utilizes a core-tree structure to efficiently update the index in response to dynamic changes in the graph. Our experimental analysis using real-world data demonstrated that the proposed method can construct indexes more efficiently than the state-of-the-art method.
graph convolution incorporates topological information of a graph into learning. Message passing corresponds to traversal of a local neighborhood in classical graph algorithms. We show that incorporating additional gl...
详细信息
ISBN:
(纸本)9798350346091
graph convolution incorporates topological information of a graph into learning. Message passing corresponds to traversal of a local neighborhood in classical graph algorithms. We show that incorporating additional global structures, such as shortest paths, through distance preserving embedding can improve performance. Our approach, Gavotte, significantly improves the performance of a range of popular graph neural networks such as GCN, GAT,graphSAGE, and GCNII for transductive learning. Gavotte also improves the performance of graph neural networks for full-supervised tasks, albeit to a smaller degree. As high-quality embeddings are generated by Gavotte as a by-product, we leverage clustering algorithms on these embeddings to augment the training set and introduce Gavotte+. Our results of Gavotte+ on datasets with very few labels demonstrate the advantage of augmenting graph convolution with distance preserving embedding.
暂无评论