Network data, represented by graph-based structures, are used in a variety of applications such as social networks and disease complication networks. A crucial task in many applications is graph ...comparison, with the goal of understanding the structural differences between pairs of graphs. However, traditional graph visualization techniques, node-link diagrams, and adjacency matrices are not intrinsically designed for comparison tasks. In this paper, we present TrammelGraph, a novel visual graph abstraction technique for graph comparison. TrammelGraph uses graph embedding and node alignment methods to create a map-based representation that eliminates visual clutter and thus facilities graph comparison. The design results in a planar graph with a regularly-spaced, crossing-free layout that helps users identify high-level topological information for graph comparison tasks. To evaluate the effectiveness of TrammelGraph, we conducted a controlled user study with 20 participants that compares TrammelGraph with node-link diagrams and adjacency matrices on a variety of common graph comparison tasks. We also conducted an expert interview with a physician using the MIMIC dataset. Both the quantitative and qualitative results from the study and interview highlighted the key strengths of TrammelGraph as a tool for visual graph comparison.
Graphic abstract
Graph kernels are of vital importance in the field of graph comparison and classification. However, how to compare and evaluate graph kernels and how to choose an optimal kernel for a practical ...classification problem remain open problems. In this paper, a comprehensive evaluation framework of graph kernels is proposed for unattributed graph classification. According to the kernel design methods, the whole graph kernel family can be categorized in five different dimensions, and then several representative graph kernels are chosen from these categories to perform the evaluation. With plenty of real-world and synthetic datasets, kernels are compared by many criteria such as classification accuracy, F1 score, runtime cost, scalability and applicability. Finally, quantitative conclusions are discussed based on the analyses of the extensive experimental results. The main contribution of this paper is that a comprehensive evaluation framework of graph kernels is proposed, which is significant for graph-classification applications and the future kernel research.
Wasserstein-Based Graph Alignment Maretic, Hermina Petric; Gheche, Mireille El; Minder, Matthias ...
IEEE transactions on signal and information processing over networks,
2022, Letnik:
8
Journal Article
Recenzirano
Odprti dostop
A novel method for comparing non-aligned graphs of various sizes is proposed, based on the Wasserstein distance between graph signal distributions induced by the respective graph Laplacian matrices. ...Specifically, a new formulation for the one-to-many graph alignment problem is casted, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. By incorporating optimal transport into our graph comparison framework, a structurally-meaningful graph distance, and a signal transportation plan that models the structure of graph data are generated. The resulting alignment problem is solved with stochastic gradient descent, where a novel Dykstra operator is used to ensure that the solution is a one-to-many (soft) assignment matrix. The performance of our novel framework is demonstrated on graph alignment, graph classification and graph signal transportation. Our method is shown to lead to significant improvements with respect to the state-of-the-art algorithms on each ofthese tasks.
Call graphs provide basis for numerous interprocedural analysers and tools, therefore it is crucial how precisely they are constructed. Developers need to know the features of a call graph builder ...before applying it to subsequent algorithms. The characteristics of call graph builders are best understood by comparing the generated call graphs themselves. The comparison can be done by matching the corresponding nodes in each graph and then analysing the found methods and calls. In this paper, we developed a process for pairing the nodes of multiple call graphs produced for the same source code. As the six static analysers that we collected for call graph building handles Java language elements differently, it was necessary to refine the basic name-wise pairing mechanism in several steps. Two language elements, the anonymous and generic methods, needed extra consideration. We describe the steps of improvement and our final solution to achieve the best possible pairing through the analysis of the Apache Commons-Math project.
Graphs are universal modeling tools. They are used to represent objects and their relationships in almost all domains: they are used to represent DNA, images, videos, social networks, XML documents, ...etc. When objects are represented by graphs, the problem of their comparison is a problem of comparing graphs. Comparing objects is a key task in our daily life. It is the core of a search engine, the backbone of a mining tool, etc. Nowadays, comparing objects faces the challenge of the large amount of data that this task must deal with. Moreover, when graphs are used to model these objects, it is known that graph comparison is very complex and computationally hard especially for large graphs. So, research on simplifying graph comparison gainedan interest and several solutions are proposed. In this paper, we explore and evaluate a new solution for the comparison of large graphs. Our approach relies on a compact encoding of graphs called prime graphs. Prime graphs are smaller and simpler than the original ones but they retain the structure and properties of the encoded graphs. We propose to approximate the similarity between two graphs by comparing the corresponding prime graphs. Simulations results show that this approach is effective for large graphs.
•A new similarity measure is proposed for large graphs.•Simplifying graph comparison known to be NP-hard especially for largest graphs.•Approximating the similarity between two graphs by comparing their prime graphs.•Primes graphs are smaller and simpler than the original ones.•Primes graphs are obtained by modular decomposition of graphs.
Graph comparison is an established NP-hard problem. In this paper, we present an efficiently scaling quantum algorithm which finds the size of the maximum common edge subgraph for any pair of ...unlabelled graphs and thus provides a meaningful measure of graph similarity. The algorithm makes use of a two-part quantum dynamic process: in the first part, we obtain information crucial for the comparison of two graphs through linear quantum computation. However, this information is hidden in the quantum system with such a vanishingly small amplitude that even quantum algorithms such as Grover’s search are not fast enough to distil it efficiently. In order to extract the information, we call upon techniques in nonlinear quantum computing to provide the speed-up necessary for an efficient algorithm. The linear quantum circuit requires
O
(
n
3
log
3
(
n
)
log
log
(
n
)
)
elementary quantum gates, and the nonlinear evolution under the Gross–Pitaevskii equation has a time scaling of
O
(
1
g
n
2
log
3
(
n
)
log
log
(
n
)
)
, where
n
is the number of vertices in each graph and
g
is the strength of the Gross–Pitaevskii nonlinearity. Through this example, we demonstrate the power of nonlinear quantum search techniques to solve a subset of NP-hard problems.
Network Embedding For Brain Connectivity Carboni, Lucrezia; Achard, Sophie; Dojat, Michel
2021 IEEE 18th International Symposium on Biomedical Imaging (ISBI),
2021-April-13
Conference Proceeding
Odprti dostop
In Neurosciences, networks are currently used for representing the brain connections system with the purpose of determining the specific characteristics of the brain itself. However, discriminating ...between a healthy human brain network and a pathological one using common network descriptors could be misleading. For this reason, we explored network embedding techniques with the purpose of brain connectivity networks comparison. We proposed first the definition of representative graph for healthy brain connectivity. Then, two classification procedures through embedding are introduced, achieving good accuracy results in different datasets. Moreover, the intriguing power of this technique is given by the possibility of visualizing networks in a low-dimensional space, facilitating the interpretation of the differences between networks under diverse conditions e.g. normal or pathological.
A main challenge in mining network-based data is finding effective ways to represent or encode graph structures so that it can be efficiently exploited by machine learning algorithms. Several methods ...have focused in network representation at node/edge or substructure level. However, many real life challenges related with time-varying, multilayer, chemical compounds and brain networks involve analysis of a family of graphs instead of single one opening additional challenges in graph comparison and representation. Traditional approaches for learning representations relies on hand-crafted specialized features to extract meaningful information about the graphs, e.g. statistical properties, structural motifs, etc. as well as popular graph distances to quantify dissimilarity between networks. In this work we provide an unsupervised approach to learn graph embeddings for a collection of graphs defined on the same set of nodes so that it can be used in numerous graph mining tasks. By using an unsupervised neural network approach on input graphs, we aim to capture the underlying distribution of the data in order to discriminate between different class of networks. Our method is assessed empirically on synthetic and real life datasets and evaluated in three different tasks: graph clustering, visualization and classification. Results reveal that our method outperforms well known graph distances and graph-kernels in clustering and classification tasks, being highly efficient in runtime.
This article proposes the tolerance nearness measure (TNM) as a computationally reduced alternative to the graph edit distance (GED) for performing graph comparisons. The TNM is defined within the ...context of near set theory, where the central idea is that determining similarity between sets of disjoint objects is at once intuitive and practically applicable. The TNM between two graphs is produced using the Bron-Kerbosh maximal clique enumeration algorithm. The result is that the TNM approach is less computationally complex than the bipartite-based GED algorithm. The contribution of this paper is the application of TNM to the problem of quantifying the similarity of disjoint graphs and that the maximal clique enumeration-based TNM produces comparable results to the GED when applied to the problem of content-based image processing, which becomes important as the number of nodes in a graph increases.
Metabolic pathways provide key information for achieving a better understanding of life and all its processes; this is useful information for the improvement of medicine, agronomy, pharmacy, and ...other similar areas. The main analysis tool used to study these pathways is based on pathway comparison, using graph data structures. Metabolic pathway comparison has been defined as a computationally complex task. In a previous work, two new algorithms were introduced to treat the problem of metabolic pathway pairwise comparison. Here we provide an extended analysis with more data and a deeper analysis of metabolic pathway comparison as listed in the discussion and results section.
PDF
