The purpose of this survey is to bring some order into the growing literature on a type of graphs which emerged in the past couple of decades under a wealth of names and in various disguises in ...different fields of mathematics and its applications. The central role is played by Sierpiński graphs, but we will also shed some light on variants of these graphs and in particular propose their classification. Concentrating on Sierpiński graphs proper we present results on their metric aspects, domination-type invariants with an emphasis on perfect codes, different colorings, and embeddings into other graphs.
The spectral theory of graphs provides a bridge between classical signal processing and the nascent field of graph signal processing. In this paper, a spectral graph analogy to Heisenberg's ...celebrated uncertainty principle is developed. Just as the classical result provides a tradeoff between signal localization in time and frequency, this result provides a fundamental tradeoff between a signal's localization on a graph and in its spectral domain. Using the eigenvectors of the graph Laplacian as a surrogate Fourier basis, quantitative definitions of graph and spectral "spreads" are given, and a complete characterization of the feasibility region of these two quantities is developed. In particular, the lower boundary of the region, referred to as the uncertainty curve, is shown to be achieved by eigenvectors associated with the smallest eigenvalues of an affine family of matrices. The convexity of the uncertainty curve allows it to be found to within ε by a fast approximation algorithm requiring O (ε -1/2 ) typically sparse eigenvalue evaluations. Closed-form expressions for the uncertainty curves for some special classes of graphs are derived, and an accurate analytical approximation for the expected uncertainty curve of Erd-s-Rényi random graphs is developed. These theoretical results are validated by numerical experiments, which also reveal an intriguing connection between diffusion processes on graphs and the uncertainty bounds.
Downsampling of signals living on a general weighted graph is not as trivial as of regular signals where we can simply keep every other samples. In this paper we propose a simple, yet effective ...downsampling scheme in which the underlying graph is approximated by a maximum spanning tree (MST) that naturally defines a graph multiresolution. This MST-based method significantly outperforms the two previous downsampling schemes, coloring-based and SVD-based, on both random and specific graphs in terms of computations and partition efficiency quantified by the graph cuts. The benefit of using MST-based downsampling for recently developed critical-sampling graph wavelet transforms in compression of graph signals is demonstrated.
Due to its ability to learn the relationship among nodes from graph data, the graph convolution network (GCN) has received extensive attention. In the machine fault diagnosis field, it needs to ...construct input graphs reflecting features and relationships of the monitoring signals. Thus, the quality of the input graph affects the diagnostic performance. But it still has two limitations: 1) the constructed input graph usually has redundant edges, consuming excessive computational costs; 2) the constructed input graph cannot reflect the relationship between the noisy signals well. In order to overcome them, a dynamic graph-based feature learning with few edges considering noisy samples is proposed for rotating machinery fault diagnosis in this article. Noisy vibration signals are converted into one spectrum feature-based static graph, where redundant edges are simplified by the distance metric function. Edge connections of the input static graph are updated according to the relationship among high-level features extracted by the GCN. Based on this, dynamic input graphs are reconstructed as new graph representations for noisy samples. To verify the effectiveness of the proposed method, validation experiments were conducted on practical platforms, and results show that the dynamic input graph with few edges can effectively improve the diagnostic performance under different SNRs.
Every critical graph is connected on proper edge-colorings of simple graphs. In contrast, there not only exist connected critical graphs but exist disconnected critical graphs on g c -colorings of ...simple graphs. In this article, disconnected g c -critical graphs are studied firstly and their structure characteristics are depicted.
We establish conditions under which the fundamental group of a graph of finite p-groups is necessarily residually p-finite. The technique of proof is independent of previously established results of ...this type, and the result is also valid for infinite graphs of groups.
A graph G = ( V, E ) is uniquely colorable if the chromatic number χ ( G ) = n and every n - coloring of G induces the same partition of V. Uniquely colorable graphs whose chromatic partition ...contains at least one γ - set is γ - uniquely colorable graphs In this paper, we characterize the planarity of γ - uniquely colorable graphs.
There are several reasons to present results as graphs, but it is not always true that graphs show the author's intent. In this column, R. Allan Reese considers examples from a popular science show
...There are several reasons to present results as graphs, but it is not always true that graphs show the author's intent. In this column, R. Allan Reese considers examples from a popular science show.
Relational machine learning studies methods for the statistical analysis of relational, or graph-structured, data. In this paper, we provide a review of how such statistical models can be "trained" ...on large knowledge graphs, and then used to predict new facts about the world (which is equivalent to predicting new edges in the graph). In particular, we discuss two fundamentally different kinds of statistical relational models, both of which can scale to massive data sets. The first is based on latent feature models such as tensor factorization and multiway neural networks. The second is based on mining observable patterns in the graph. We also show how to combine these latent and observable models to get improved modeling power at decreased computational cost. Finally, we discuss how such statistical models of graphs can be combined with text-based information extraction methods for automatically constructing knowledge graphs from the Web. To this end, we also discuss Google's knowledge vault project as an example of such combination.
PDF
