Search

In this article, we give characterization for existence of quantum fractional revival in unitary Cayley graph utilizing adjacency matrix Hamiltonian. Unitary Cayley graph $X=( Z_n, S)$ is a special graph as connection set $S \subseteq Z_n$ is the collection of coprimes to $n$. Unitary Cayley graph is an integral graph and its adjacency matrix is a circulant one. We prove that quantum fractional revival in unitary Cayley graphs exists only when the number of vertices is even. Number-theoretic and spectral characterizations are given for unitary Cayley graph admitting quantum fractional revival. Quantum fractional revival is analogous to quantum entanglement. It is one of qubit state transfer phenomena useful in communication of quantum information.

In a recent article "Projective geometries, $Q$-polynomial structures, and quantum groups" Terwilliger (arXiv:2407.14964) defined a certain weighted adjacency matrix, depending on a free (positive real) parameter, associated with the projective geometry, and showed (among many other results) that it is diagonalizable, with the eigenvalues and their multiplicities explicitly written down, and that it satisfies the $Q$-polynomial property (with respect to the zero subspace). In this note we (i) Write down an explicit eigenbasis for this matrix. (ii) Evaluate the adjacency matrix-eigenvector products, yielding a new proof for the eigenvalues and their multiplicities. (iii) Evaluate the dual adjacency matrix-eigenvector products and directly show that the action of the dual adjacency matrix on the eigenspaces of the adjacency matrix is block-tridiagonal, yielding a new proof of the $Q$-polynomial property., Comment: arXiv admin note: substantial text overlap with arXiv:2204.05540

We study the holomorphic functional calculus for the adjacency matrices on possibly infinite regular graphs. More precisely, we show an expansion of $h(A)$ in terms of non-backtracking matrices, where $A$ is the adjacency matrix and $h$ is a holomorphic function on the interior of a particular ellipse containing the spectrum of $A$. Furthermore, we prove related trace formulas for regular graphs. Our results provide a simple and direct approach to the study of resolvent, heat and Schr\"odinger equations, Ihara zeta functions, and combinatorial enumeration problems on regular graphs., Comment: 38 pages. The article has been updated and restructured. All comments are welcome

Mobile apps and wearable devices accurately and continuously measure human activity; patterns within this data can provide a wealth of information applicable to fields such as transportation and health. Despite the potential utility of this data, there has been limited development of analysis methods for sequences of daily activities. In this paper, we propose a novel clustering method and cluster evaluation metric for human activity data that leverages an adjacency matrix representation to cluster the data without the calculation of a distance matrix. Our technique is substantially faster than conventional methods based on computing pairwise distances via sequence alignment algorithms and also enhances interpretability of results. We compare our method to distance-based hierarchical clustering and nTreeClus through simulation studies and an application to data collected by Daynamica, an app that turns sensor data into a daily summary of a user's activities. Among days that contain a large portion of time spent at home, our method distinguishes days that also contain multiple hours of travel or other activities, while both comparison methods fail to identify these patterns. We further identify which day patterns classified by our method are associated with higher concern for contracting COVID-19 with implications for public health messaging.

In the realm of applications where data dynamically evolves across spatial and temporal dimensions, Graph Neural Networks (GNNs) are often complemented by sequence modeling architectures, such as RNNs and transformers, to effectively model temporal changes. These hybrid models typically arrange the spatial and temporal learning components in series. A pioneering effort to jointly model the spatio-temporal dependencies using only GNNs was the introduction of the Block Adjacency Matrix \(\mathbf{A_B}\) \cite{1}, which was constructed by diagonally concatenating adjacency matrices from graphs at different time steps. This approach resulted in a single graph encompassing complete spatio-temporal data; however, the graphs from different time steps remained disconnected, limiting GNN message-passing to spatially connected nodes only. Addressing this critical challenge, we propose a novel end-to-end learning architecture specifically designed to mend the temporal dependencies, resulting in a well-connected graph. Thus, we provide a framework for the learnable representation of spatio-temporal data as graphs. Our methodology demonstrates superior performance on benchmark datasets, such as SurgVisDom and C2D2, surpassing existing state-of-the-art graph models in terms of accuracy. Our model also achieves significantly lower computational complexity, having far fewer parameters than methods reliant on CLIP and 3D CNN architectures., Comment: Accepted at ICONIP 2024

The problem of finding the connected components of a graph is considered. The algorithms addressed to solve the problem are used to solve such problems on graphs as problems of finding points of articulation, bridges, maximin bridge, etc. A natural approach to solving this problem is a breadth-first search, the implementations of which are presented in software libraries designed to maximize the use of the capabi\-lities of modern computer architectures. We present an approach using perturbations of adjacency matrix of a graph. We check wether the graph is connected or not by comparing the solutions of the two systems of linear algebraic equations (SLAE): the first SLAE with a perturbed adjacency matrix of the graph and the second SLAE with~unperturbed matrix. This approach makes it possible to use effective numerical implementations of SLAE solution methods to solve connectivity problems on graphs. Iterations of iterative numerical methods for solving such SLAE can be considered as carrying out a graph traversal. Generally speaking, the traversal is not equivalent to the traversal that is carried out with breadth-first search. An algorithm for finding the connected components of a graph using such a traversal is presented. For any instance of the problem, this algorithm has no greater computational complexity than breadth-first search, and for~most individual problems it has less complexity., Comment: 22 pages, 4 figures

To improve the robustness of graph neural networks (GNN), graph structure learning (GSL) has attracted great interest due to the pervasiveness of noise in graph data. Many approaches have been proposed for GSL to jointly learn a clean graph structure and corresponding representations. To extend the previous work, this paper proposes a novel regularized GSL approach, particularly with an alignment of feature information and graph information, which is motivated mainly by our derived lower bound of node-level Rademacher complexity for GNNs. Additionally, our proposed approach incorporates sparse dimensional reduction to leverage low-dimensional node features that are relevant to the graph structure. To evaluate the effectiveness of our approach, we conduct experiments on real-world graphs. The results demonstrate that our proposed GSL method outperforms several competitive baselines, especially in scenarios where the graph structures are heavily affected by noise. Overall, our research highlights the importance of integrating feature and graph information alignment in GSL, as inspired by our derived theoretical result, and showcases the superiority of our approach in handling noisy graph structures through comprehensive experiments on real-world datasets.

Despite the recent advances in deep neural networks, standard convolutional kernels limit the applications of these networks to the Euclidean domain only. Considering the geodesic nature of the measurement of the earth's surface, remote sensing is one such area that can benefit from non-Euclidean and spherical domains. For this purpose, we propose a novel Graph Neural Network architecture for spatial and spatio-temporal classification using satellite imagery. We propose a hybrid attention method to learn the relative importance of irregular neighbors in remote sensing data. Instead of classifying each pixel, we propose a method based on Simple Linear Iterative Clustering (SLIC) image segmentation and Graph Attention GAT. The superpixels obtained from SLIC become the nodes of our Graph Convolution Network (GCN). We then construct a region adjacency graph (RAG) where each superpixel is connected to every other adjacent superpixel in the image, enabling information to propagate globally. Finally, we propose a Spatially driven Attention Graph Neural Network (SAG-NN) to classify each RAG. We also propose an extension to our SAG-NN for spatio-temporal data. Unlike regular grids of pixels in images, superpixels are irregular in nature and cannot be used to create spatio-temporal graphs. We introduce temporal bias by combining unconnected RAGs from each image into one supergraph. This is achieved by introducing block adjacency matrices resulting in novel Spatio-Temporal driven Attention Graph Neural Network with Block Adjacency matrix (STAG-NN-BA). We evaluate our proposed methods on two remote sensing datasets namely Asia14 and C2D2. In comparison with both non-graph and graph-based approaches our SAG-NN and STAG-NN-BA achieved superior accuracy on all the datasets while incurring less computation cost. The code and dataset will be made public via our GitHub repository.

The use of complex networks as a modern approach to understanding the world and its dynamics is well-established in literature. The adjacency matrix, which provides a one-to-one representation of a complex network, can also yield several metrics of the graph. However, it is not always clear that this representation is unique, as the permutation of lines and rows in the matrix can represent the same graph. To address this issue, the proposed methodology employs a sorting algorithm to rearrange the elements of the adjacency matrix of a complex graph in a specific order. The resulting sorted adjacency matrix is then used as input for feature extraction and machine learning algorithms to classify the networks. The results indicate that the proposed methodology outperforms previous literature results on synthetic and real-world data., Comment: 12 pages, 10 figures

In this article we establish relationships between Leavitt path algebras, talented monoids and the adjacency matrices of the underlying graphs. We show that indeed the adjacency matrix generates in some sense the group action on the generators of the talented monoid. With the help of this we deduce a form of the aperiodicity index of a graph via the talented monoid. We classify hereditary and saturated subsets via the adjacency matrix. Moreover we give a formula to compute all paths of a given length in a Leavitt path algebra based on the adjacency matrix. In addition we discuss the number of cycles in a graph. In particular we give an equivalent characterization of acylic graphs via the adjacency matrix, the talented monoid and the Leavitt path algebra.

This study is on the enumeration of spatial robotic manipulators, which is an essential basis for a companion study on dimensional synthesis, both of which together present a wider utility in manipulator synthesis. The enumeration of manipulators is done by using adjacency matrix concept. In this paper, a novel way of applying adjacency matrix to spatial manipulators with four types of joints, namely revolute, prismatic, cylindrical and spherical joints, is presented. The limitations of the applicability of the concept to 3D manipulators are discussed. 1-DOF (Degree Of Freedom) manipulators of four links and 2-DOF, 3-DOF and 4-DOF manipulators of three links, four links and five links, are enumerated based on a set of conventions and some assumptions. Finally, 96 1-DOF manipulators of four links, 641 2-DOF manipulators of 5 links, 4 2-DOF manipulators of three links, 8 3-DOF manipulators of four links and 15 4-DOF manipulators of five links are presented.

The fact that the adjacency matrix of every finite graph is diagonalizable plays a fundamental role in spectral graph theory. Since this fact does not hold in general for digraphs, it is natural to ask whether it holds for digraphs with certain level of symmetry. Interest on this question dates back to early 1980s, when P.~J.~Cameron asked for the existence of arc-transitive digraphs with non-diagonalizable adjacency matrix. This was answered in the affirmative by L.~Babai in 1985. Then Babai posed the open problem of constructing a 2-arc-transitive digraph and a vertex-primitive digraph whose adjacency matrices are not diagonalizable. In this paper, we solve Babai's problem by constructing an infinite family of $s$-arc-transitive digraphs for each integer $s\geq2$, and an infinite family of vertex-primitive digraphs, respectively, both of whose adjacency matrices are non-diagonalizable.

Human skeleton data has received increasing attention in action recognition due to its background robustness and high efficiency. In skeleton-based action recognition, graph convolutional network (GCN) has become the mainstream method. This paper analyzes the fundamental factor for GCN-based models -- the adjacency matrix. We notice that most GCN-based methods conduct their adjacency matrix based on the human natural skeleton structure. Based on our former work and analysis, we propose that the human natural skeleton structure adjacency matrix is not proper for skeleton-based action recognition. We propose a new adjacency matrix that abandons all rigid neighbor connections but lets the model adaptively learn the relationships of joints. We conduct extensive experiments and analysis with a validation model on two skeleton-based action recognition datasets (NTURGBD60 and FineGYM). Comprehensive experimental results and analysis reveals that 1) the most widely used human natural skeleton structure adjacency matrix is unsuitable in skeleton-based action recognition; 2) The proposed adjacency matrix is superior in model performance, noise robustness and transferability., Comment: 19 pages

The $\alpha$-Hermitian adjacency matrix $H_\alpha$ of a mixed graph $X$ has been recently introduced. It is a generalization of the adjacency matrix of unoriented graphs. In this paper, we consider a special case of the complex number $\alpha$. This enables us to define an incidence matrix of mixed graphs. Consequently, we define a generalization of line graphs as well as a generalization of the signless Laplacian adjacency matrix of graphs. We then study the spectral properties of the signless Laplacian adjacency matrix of a mixed graph. Lastly, we characterize when the signless Laplacian adjacency matrix of a mixed graph is singular and give lower and upper bounds of number of arcs and digons in terms of largest and lowest eigenvalue of the signless Laplacian adjacency matrix.

Let $X$ be bipartite mixed graph and for a unit complex number $\alpha$, $H_\alpha$ be its $\alpha$-hermitian adjacency matrix. If $X$ has a unique perfect matching, then $H_\alpha$ has a hermitian inverse $H_\alpha^{-1}$. In this paper we give a full description of the entries of $H_\alpha^{-1}$ in terms of the paths between the vertices. Furthermore, for $\alpha$ equals the primitive third root of unity $\gamma$ and for a unicyclic bipartite graph $X$ with unique perfect matching, we characterize when $H_\gamma^{-1}$ is $\pm 1$ diagonally similar to $\gamma$-hermitian adjacency matrix of a mixed graph. Through our work, we have provided a new construction for the $\pm 1$ diagonal matrix.

We define a q-analog of the adjacency matrix of the n-cube, determine its eigenvalues and write down a canonical eigenbasis. We give a weighted count of the number of rooted spanning trees in the q-analog of the n-cube. Remarks on the previous version: The q-analog of the Kac matrix appears in Terwilliger's classification of Leonard pairs and as such its eigenvalues and eigenvectors were known. Reference added to Terwilliger's papers and also to a paper of Johnson. Title changed to reflect this.

We look for a non-zero $(0, 1)$-vector in the row space of the adjacency matrix $A(\Gamma)$ of a graph $\Gamma,$ provided $\Gamma$ has at least one edge. Akbari, Cameron, and Khosrovshahi conjectured that there exists a non-zero $(0,1)$-vector in the row space of $A(\Gamma)$ (over the real numbers) which does not occur as a row of $A(\Gamma).$ This conjecture can be easily verified for graphs having diameter is equal to $1$ (complete graphs). In this article, we affirmatively prove this conjecture for any graph whose diameter is $\geq 4.$ Furthermore, in the remaining two cases that is, for graphs with diameter is equal to $2$ or $3,$ we report some progress in support of the conjecture., Comment: 16 pages, 7figures

In this paper, we found the Moore-Penrose generalized inverse of adjacency matrix of an undirected graph, explicitly. We proved that the matrix $R_\lambda= [r_{ij}]$ is nonsingular where $r_{ii}=\frac{1}{\lambda}+ \deg v_i$ and $r_{ij}=\mid N_G(V_i)\cap N_G(V_j)\mid$ for $i\neq j$, and we proved that $A^{\dagger}_G=[s_{ij}]_{1\leq i, j \leq n}$ where $\displaystyle{s_{ij}=s_{ji}=\lim_{\lambda \rightarrow +\infty} \langle R^{-1}_{\lambda}e_j, f_i \rangle }$. The proof of the main result was based on the Tikhonov regularization., Comment: 6, articles