(Meta) Kernelization Bodlaender, Hans L; Fomin, Fedor V; Lokshtanov, Daniel ...
Journal of the ACM,
12/2016, Volume:
63, Issue:
5
Journal Article
Peer reviewed
Open access
In a parameterized problem, every instance I comes with a positive integer k. The problem is said to admit a polynomial kernel if, in polynomial time, one can reduce the size of the instance I to a ...polynomial in k while preserving the answer. In this work, we give two meta-theorems on kernelization. The first theorem says that all problems expressible in counting monadic second-order logic and satisfying a coverability property admit a polynomial kernel on graphs of bounded genus. Our second result is that all problems that have finite integer index and satisfy a weaker coverability property admit a linear kernel on graphs of bounded genus. These theorems unify and extend all previously known kernelization results for planar graph problems.
In this paper, we discuss distributed optimization over directed graphs, where doubly stochastic weights cannot be constructed. Most of the existing algorithms overcome this issue by applying ...push-sum consensus, which utilizes column-stochastic weights. The formulation of column-stochastic weights requires each agent to know (at least) its out-degree, which may be impractical in, for example, broadcast-based communication protocols. In contrast, we describe FROST (Fast Row-stochastic-Optimization with uncoordinated STep-sizes), an optimization algorithm applicable to directed graphs that does not require the knowledge of out-degrees, the implementation of which is straightforward as each agent locally assigns weights to the incoming information and locally chooses a suitable step-size. We show that FROST converges linearly to the optimal solution for smooth and strongly convex functions given that the largest step-size is positive and sufficiently small.
This book is about graph energy. The authors have included many of the important results on graph energy, such as the complete solution to the conjecture on maximal energy of unicyclic graphs, the ...Wagner-Heubergers result on the energy of trees, the energy of random graphs or the approach to energy using singular values. It contains an extensive coverage of recent results and a gradual development of topics and the inclusion of complete proofs from most of the important recent results in the area. The latter fact makes it a valuable reference for researchers looking to get into the field of graph energy, further stimulating it with occasional inclusion of open problems. The book provides a comprehensive survey of all results and common proof methods obtained in this field with an extensive reference section. The book is aimed mainly towards mathematicians, both researchers and doctoral students, with interest in the field of mathematical chemistry.
Graph representation learning aims to represent the structural and semantic information of graph objects as dense real value vectors in low dimensional space by machine learning. It is widely used in ...node classification, link prediction, and recommendation systems. However, directly computing the embeddings for original graphs is prohibitively inefficient, especially for large-scale graphs. To address this issue, we present the GSE (Graph Summarization Embedding) model, a more efficient model that computes the nodes' embeddings based on graph summarization. Specifically, the model first searches for the minimum information entropy of <inline-formula> <tex-math notation="LaTeX">k </tex-math></inline-formula> groups to transform the original graph into a hypergraph with higher-order structural features. Next, the summarization graph's connection probabilities are used to determine the biased random walks on the hypergraph, which then generates the sequences of the super-nodes. Finally, the node sequences are fed into the skip-gram to generate the vectors of these nodes. Our proposed model improves the efficiency of graph embedding on big data graphs and effectively alleviates the local optimal problem caused by the random walks. Experimental results demonstrate that GSE outperforms main existing clustering baselines, such as K_Means Clustering, Affinity Propagation Clustering, Canopy Clustering, and ACP Clustering. Moreover, our model can be coupled with the main graph embedding methods and improves the Macro-F1 scores and Micro-F1 scores for classification tasks on a variety of real-world graph data.
Embedding Grid Graphs on Surfaces Millichap, Christian; Salinas, Fabian
Graphs and combinatorics,
06/2022, Volume:
38, Issue:
3
Journal Article
Peer reviewed
Open access
In this paper, we analyze embeddings of grid graphs on orientable surfaces. We determine the genus of two infinite classes of 3-dimensional grid graphs that do not admit quadrilateral embeddings and ...effective upper bounds for the genus of any 3-dimensional grid graph, both in terms of a grid graph’s combinatorics. As an application, we provide a complete classification of planar and toroidal grid graphs. Our work requires a variety of combinatorial and graph theoretic arguments to determine effective lower bounds on the genus of a grid graph, along with explicitly constructing embeddings of grid graphs on surfaces to determine effective upper bounds on their genera.
This work explores the properties of the edge variant of the graph Laplacian in the context of the edge agreement problem. We show that the edge Laplacian, and its corresponding agreement protocol, ...provides a useful perspective on the well-known node agreement, or the consensus algorithm. Specifically, the dynamics induced by the edge Laplacian facilitates a better understanding of the role of certain subgraphs, e.g., cycles and spanning trees, in the original agreement problem. Using the edge Laplacian, we proceed to examine graph-theoretic characterizations of the H 2 and H ∞ performance for the agreement protocol. These results are subsequently applied in the contexts of optimal sensor placement for consensus-based applications. Finally, the edge Laplacian is employed to provide new insights into the nonlinear extension of linear agreement to agents with passive dynamics.
This paper provides an extensive overview of the use of knowledge graphs in the context of Explainable Machine Learning. As of late, explainable AI has become a very active field of research by ...addressing the limitations of the latest machine learning solutions that often provide highly accurate, but hardly scrutable and interpretable decisions.
An increasing interest has also been shown in the integration of Knowledge Representation techniques in Machine Learning applications, mostly motivated by the complementary strengths and weaknesses that could lead to a new generation of hybrid intelligent systems. Following this idea, we hypothesise that knowledge graphs, which naturally provide domain background knowledge in a machine-readable format, could be integrated in Explainable Machine Learning approaches to help them provide more meaningful, insightful and trustworthy explanations.
Using a systematic literature review methodology we designed an analytical framework to explore the current landscape of Explainable Machine Learning. We focus particularly on the integration with structured knowledge at large scale, and use our framework to analyse a variety of Machine Learning domains, identifying the main characteristics of such knowledge-based, explainable systems from different perspectives. We then summarise the strengths of such hybrid systems, such as improved understandability, reactivity, and accuracy, as well as their limitations, e.g. in handling noise or extracting knowledge efficiently. We conclude by discussing a list of open challenges left for future research.
Operations on Soft Graphs Akram, Muhammad; Nawaz, Saira
Fuzzy information and engineering,
December 2015, 2015-12-00, 20151201, 2015-12-01, Volume:
7, Issue:
4
Journal Article
Peer reviewed
Open access
Mathematical modelling, analysis and computing of problems with uncertainty is one of the hottest areas in interdisciplinary research involving applied mathematics, computational intelligence and ...decision sciences. It is worth noting that uncertainty arises from various domains has very different nature and cannot be captured within a single mathematical framework. Molodtsov’s soft sets provide us a new way of coping with uncertainty from the viewpoint of parameterization. In this paper, we introduce the concepts of soft graphs, vertex-induced soft graphs, edge-induced soft graphs and describe some operations on soft graphs by presenting several examples to demonstrate these new concepts. Finally, we investigate some fundamental properties of soft graphs.
A celebrated theorem of Stiebitz 13 asserts that any graph with minimum degree at least s+t+1 can be partitioned into two parts that induce two subgraphs with minimum degree at least s and t, ...respectively. This resolved a conjecture of Thomassen. In this article, we prove that for s,t≥2, if a graph G contains no cycle of length four and has minimum degree at least s+t−1, then G can be partitioned into two parts that induce two subgraphs with minimum degree at least s and t, respectively. This improves the result of Diwan in 5, where he proved the same statement for graphs of girth at least five. Our proof also works for the case of variable functions, in which the bounds are sharp as showing by some polarity graphs.
In 1962, Oystein Ore asked in which graphs there is exactly one geodesic (a shortest path) between any two vertices. He called such graphs geodetic. In this paper, we systematically study properties ...of geodetic graphs, and also consider antipodal graphs, in which each vertex has exactly one antipode (a farthest vertex). We find necessary and sufficient conditions for a graph to be geodetic or antipodal, obtain results related to algorithmic construction, and find interesting families of Hamiltonian geodetic graphs. By introducing and describing the maximal hereditary subclasses and the minimal hereditary superclasses of the geodetic and antipodal graphs, we get close to the goal of our research – a constructive classification of these graphs.
PDF
