A graph
G
is said to be
distance
d
matchable if, for any matching
M
of
G
in which edges are pairwise at least distance
d
apart, there exists a perfect matching
M
∗
of
G
which contains
M
. In this ...paper, we prove the following results: (i) if
G
is a cubic bipartite graph in which, for each
e
∈
E
(
G
)
, there exist two cycles
C
1
,
C
2
of length at most
d
such that
E
(
C
1
)
∩
E
(
C
2
)
=
{
e
}
, then
G
is distance
d
-
1
matchable, and (ii) if
G
is a planar or projective planar cubic bipartite graph in which, for each
e
∈
E
(
G
)
, there exist two cycles
C
1
,
C
2
of length at most 6 such that
e
∈
E
(
C
1
)
∩
E
(
C
2
)
, then
G
is distance 6 matchable.
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.
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.
Graphs are versatile tools for representing structured data. As a result, a variety of machine learning methods have been studied for graph data analysis. Although many such learning methods depend ...on the measurement of differences between input graphs, defining an appropriate distance metric for graphs remains a controversial issue. Hence, we propose a supervised distance metric learning method for the graph classification problem. Our method, named
interpretable graph metric learning
(IGML), learns discriminative metrics in a subgraph-based feature space, which has a strong graph representation capability. By introducing a sparsity-inducing penalty on the weight of each subgraph, IGML can identify a small number of important subgraphs that can provide insight into the given classification task. Because our formulation has a large number of optimization variables, an efficient algorithm that uses pruning techniques based on
safe screening
and
working set selection
methods is also proposed. An important property of IGML is that solution optimality is guaranteed because the problem is formulated as a convex problem and our pruning strategies only discard unnecessary subgraphs. Furthermore, we show that IGML is also applicable to other structured data such as itemset and sequence data, and that it can incorporate vertex-label similarity by using a transportation-based subgraph feature. We empirically evaluate the computational efficiency and classification performance of IGML on several benchmark datasets and provide some illustrative examples of how IGML identifies important subgraphs from a given graph dataset.
GRAPHS DETERMINED BY THEIR -GAIN SPECTRA WANG, SAI; WONG, DEIN; TIAN, FENGLEI
Bulletin of the Australian Mathematical Society,
04/2021, Volume:
103, Issue:
2
Journal Article
Peer reviewed
Abstract
An undirected graph
$G$
is determined by its
$T$
-gain spectrum (DTS) if every
$T$
-gain graph cospectral to
$G$
is switching equivalent to
$G$
. We show that the complete graph
$K_{n}$
and ...the graph
$K_{n}-e$
obtained by deleting an edge from
$K_{n}$
are DTS, the star
$K_{1,n}$
is DTS if and only if
$n\leq 2$
, and an odd path
$P_{2m+1}$
is not DTS if
$m\geq 2$
. We give an operation for constructing cospectral
$T$
-gain graphs and apply it to show that a tree of arbitrary order (at least
$5$
) is not DTS.
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.
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 survey concerns regular graphs that are extremal with respect to the number of independent sets and, more generally, graph homomorphisms. More precisely, in the family of of d-regular graphs, ...which graph G maximizes/minimizes the quantity i(G)
1/v(G)
, the number of independent sets in G normalized exponentially by the size of G? What if i(G) is replaced by some other graph parameter? We review existing techniques, highlight some exciting recent developments, and discuss open problems and conjectures for future research.
PDF
