This paper proposes a family of Aligned Entropic Graph Kernels (AEGK) for graph classification, based on the Averaged Mixing Matrix (AMM) of Continuous-time Quantum Walks (CTQWs). Specifically, we show how the AMM matrix allows us to compute a quantum Shannon entropy of each vertex for either un-attributed or attributed graphs. For pairwise graphs, the proposed AEGK kernels are defined by computing the kernel-based similarity between the quantum Shannon entropies of their pairwise aligned vertices. Theoretical analysis reveals that the AEGK kernels can not only integrate the structural correspondence information between graphs, but also discriminate the structural differences between aligned vertices. Moreover, the AEGK kernels can simultaneously capture both global and local structural characteristics through the quantum Shannon entropies. These theoretical properties explain the effectiveness.

This paper proposes a family of Hierarchical Aligned Quantum Jensen-Shannon Kernels (HAQJSK) for un-attributed graphs. The HAQJSK kernels can incorporate hierarchical correspondence information between graphs, and thus transform arbitrary sized graphs into fix-sized aligned structures, i.e., the hierarchical transitive aligned Adjacency Matrix of vertices or Density Matrix of Continuous-Time Quantum Walks (CTQWs). For pairwise graphs, the resulting HAQJSK kernels are defined by computing the Quantum Jensen-Shannon Divergence (QJSD) between their aligned structures. Unlike classical graph kernels, the HAQJSK kernels can either reflect global intrinsic structure characteristics through CTQWs, or address the drawback of neglecting structural correspondence information, theoretically explaining the effectiveness.

In this work, we develop a family of Aligned Entropic Graph Kernels (AEGK) for graph classification. We commence by performing the Continuous-time Quantum Walk (CTQW) on each graph structure, and compute the Averaged Mixing Matrix (AMM) to describe how the CTQW visits all vertices from a starting vertex. More specifically, we show how this AMM matrix allows us to compute a quantum Shannon entropy of each vertex for either un-attributed or attributed graphs. For pairwise graphs, the proposed AEGK kernels are defined by computing the kernel-based similarity between the quantum Shannon entropies of their pairwise aligned vertices. The analysis of theoretical properties reveals that the proposed AEGK kernels cannot only address the shortcoming of neglecting the structural correspondence information between graphs arising in most existing R-convolution graph kernels, but also overcome the problems of neglecting the structural differences and vertex-attributed information arising in existing vertex-based matching kernels. Moreover, unlike most existing classical graph kernels that only focus on the global or local structural information of graphs, the proposed AEGK kernels can simultaneously capture both global and local structural characteristics through the quantum Shannon entropies, reflecting more precise kernel-based similarity measures between pairwise graphs. The above theoretical properties explain the effectiveness of the proposed AEGK kernels. Experimental evaluations demonstrate that the proposed kernels can outperform state-of-the-art graph kernels and deep learning models for graph classification.

In this work, we propose two novel quantum walk kernels, namely the Hierarchical Aligned Quantum Jensen-Shannon Kernels (HAQJSK), between un-attributed graph structures. Different from most classical graph kernels, the proposed HAQJSK kernels can incorporate hierarchical aligned structure information between graphs and transform graphs of random sizes into fixed-size aligned graph structures, i.e., the Hierarchical Transitive Aligned Adjacency Matrix of vertices and the Hierarchical Transitive Aligned Density Matrix of the Continuous-Time Quantum Walks (CTQW). With pairwise graphs to hand, the resulting HAQJSK kernels are defined by computing the Quantum Jensen-Shannon Divergence (QJSD) between their transitive aligned graph structures. We show that the proposed HAQJSK kernels not only reflect richer intrinsic whole graph characteristics in terms of the CTQW, but also address the drawback of neglecting structural correspondence information that arises in most R-convolution graph kernels. Moreover, unlike the previous QJSD based graph kernels associated with the QJSD and the CTQW, the proposed HAQJSK kernels can simultaneously guarantee the properties of permutation invariant and positive definiteness, explaining the theoretical advantages of the HAQJSK kernels. The experiment indicates the effectiveness of the new proposed kernels.

To ease the process of building Knowledge Graphs (KGs) from scratch, a cost-effective method is required to enrich a KG using the triples extracted from a corpus. However, it is challenging to enrich a KG with newly extracted triples since they contain noisy information. This paper proposes to refine a KG by leveraging information extracted from a corpus. In particular, we first formulate the task of building KGs as two coupled sub-tasks, namely join event extraction and knowledge graph fusion. We then propose a collaborative knowledge graph fusion framework, which is composed of an explorer and a supervisor, to allow the involved two sub-tasks to mutually assist each other in an alternative manner. More concretely, an explorer extracts triples from a corpus supervised by both the ground-truth annotation and the KG provided by the supervisor. Furthermore, a supervisor then evaluates the extracted triples and enriches the KG with those that are highly ranked. To implement this evaluation, we further propose a translated relation alignment scoring mechanism to align and translate the extracted triples to the KG. Experimental results verify that this collaboration can improve both the performance of our sub-tasks, and contribute to high-quality enriched knowledge graphs.

This paper proposes a new Quantum Spatial Graph Convolutional Neural Network (QSGCNN) model that can directly learn a classification function for graphs of arbitrary sizes. Unlike state-of-the-art Graph Convolutional Neural Network (GCNN) models, the proposed QSGCNN model incorporates the process of identifying transitive aligned vertices between graphs and transforms arbitrary sized graphs into fixed-sized aligned vertex grid structures. In order to learn representative graph characteristics, a new quantum spatial graph convolution is proposed and employed to extract multi-scale vertex features, in terms of quantum information propagation between grid vertices of each graph. Since the quantum spatial convolution preserves the grid structures of the input vertices (i.e., the convolution layer does not alter the original spatial position of vertices), the proposed QSGCNN model allows to directly employ the traditional convolutional neural network architecture to further learn from the global graph topology, providing an end-to-end deep learning architecture that integrates the graph representation and learning in the quantum spatial graph convolution layer and the traditional convolutional layer for graph classifications. We indicate the effectiveness of the proposed QSGCNN model in relation to existing state-of-the-art methods. Experiments on benchmark graph classification datasets demonstrate the effectiveness of the proposed QSGCNN model.

This paper proposes a novel Quantum Spatial Graph Convolutional Neural Network (QSGCNN) model that can directly learn a classification function for graphs of arbitrary sizes. The main idea is to define a new quantum-inspired spatial graph convolution associated with pre-transformed fixed-sized aligned grid structures of graphs, in terms of quantum information propagation between grid vertices of each graph. We show that the proposed QSGCNN model can significantly reduce either the information loss or the notorious tottering problem arising in existing spatially-based Graph Convolutional Network (GCN) models. Experiments on benchmark graph datasets demonstrate the effectiveness of the proposed QSGCNN model.

Quantification of symmetries in complex networks is typically done globally in terms of automorphisms. Extending previous methods to locally assess the symmetry of nodes is not straightforward. Here we present a new framework to quantify the symmetries around nodes, which we call connectivity patterns. We develop two topological transformations that allow a concise characterization of the different types of symmetry appearing on networks and apply these concepts to six network models, namely the Erd\H{o}s-R\'enyi, Barab\'asi-Albert, random geometric graph, Waxman, Voronoi and rewired Voronoi. Real-world networks, namely the scientific areas of Wikipedia, the world-wide airport network and the street networks of Oldenburg and San Joaquin, are also analyzed in terms of the proposed symmetry measurements. Several interesting results emerge from this analysis, including the high symmetry exhibited by the Erd\H{o}s-R\'enyi model. Additionally, we found that the proposed measurements present low correlation with other traditional metrics, such as node degree and betweenness centrality. Principal component analysis is used to combine all the results, revealing that the concepts presented here have substantial potential to also characterize networks at a global scale.