Search

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

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 through simulation studies and an application to data collected by Daynamica, an app that turns raw 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 full-time work or multiple hours of travel, while hierarchical clustering groups these days together. We also illustrate how the computational advantage of our method enables the analysis of longer sequences by clustering full weeks of activity data.

In recent work, [1] introduced the concept of using a Block Adjacency Matrix (BA) for the representation of spatio-temporal data. While their method successfully concatenated adjacency matrices to encapsulate spatio-temporal relationships in a single graph, it formed a disconnected graph. This limitation hampered the ability of Graph Convolutional Networks (GCNs) to perform message passing across nodes belonging to different time steps, as no temporal links were present. To overcome this challenge, we introduce an encoder block specifically designed to learn these missing temporal links. The encoder block processes the BA and predicts connections between previously unconnected subgraphs, resulting in a Spatio-Temporal Block Adjacency Matrix (STBAM). This enriched matrix is then fed into a Graph Neural Network (GNN) to capture the complex spatio-temporal topology of the network. Our evaluations on benchmark datasets, surgVisDom and C2D2, demonstrate that our method, with slightly higher complexity, achieves superior results compared to state-of-the-art results. Our approach's computational overhead remains significantly lower than conventional non-graph-based methodologies for spatio-temporal data., Comment: Submitted to ICASSP 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

Let $G$ be a finite tree. For any matching $M$ of $G$, let $U(M)$ be the set of vertices uncovered by $M$. Let $\mathcal{M}_G$ be a uniform random maximum size matching of $G$. In this paper, we analyze the structure of $U(\mathcal{M}_G)$. We first show that $U(\mathcal{M}_G)$ is a determinantal process. We also show that for most vertices of $G$, the process $U(\mathcal{M}_G)$ in a small neighborhood of that vertex can be well approximated based on a somewhat larger neighborhood of the same vertex. Then we show that the normalized Shannon entropy of $U(\mathcal{M}_G)$ can be also well approximated using the local structure of $G$. In other words, in the realm of trees, the normalized Shannon entropy of $U(\mathcal{M}_G)$ -- that is, the normalized logarithm of the number of maximum size matchings of $G$ -- is a Benjamini-Schramm continuous parameter. We show that $U(\mathcal{M}_G)$ is a determinantal process through establishing a new connection between $U(\mathcal{M}_G)$ and the adjacency matrix of $G$. This result sheds a new light on the well-known fact that on a tree, the number of vertices uncovered by a maximum size matching is equal to the nullity of the adjacency matrix. Some of the proofs are based on the well established method of introducing a new perturbative parameter, which we call temperature, and then define the positive temperature analogue of $\mathcal{M}_G$, the so called monomer-dimer model, and let the temperature go to zero.

This contribution gives an extensive study on spectra of mixed graphs via its Hermitian adjacency matrix of the second kind { ($N$-matrix for short)} introduced by Mohar \cite{0001}. This matrix is indexed by the vertices of the mixed graph, and the entry corresponding to an arc from $u$ to $v$ is equal to the sixth root of unity $\omega=\frac{1+{\bf i}\sqrt{3}}{2}$ (and its symmetric entry is $\bar{\omega}=\frac{1-{\bf i}\sqrt{3}}{2}$); the entry corresponding to an undirected edge is equal to 1, and 0 otherwise. The main results of this paper include the following: {equivalent} conditions for a mixed graph that shares the same spectrum of its $N$-matrix with its underlying graph are given. A sharp upper bound on the spectral radius is established and the corresponding extremal mixed graphs are identified. Operations which are called two-way and three-way switchings are discussed--they give rise to some cospectral mixed graphs. We extract all the mixed graphs whose rank of its $N$-matrix is $2$ (resp. 3). Furthermore, we show that {if $M_G$ is a connected mixed graph with rank $2,$ then $M_G$ is switching equivalent to each connected mixed graph to which it is cospectral}. However, this does not hold for some connected mixed graphs with rank $3$. We identify all mixed graphs whose eigenvalues of its $N$-matrix lie in the range $(-\alpha,\, \alpha)$ for $\alpha\in\left\{\sqrt{2},\,\sqrt{3},\,2\right\}$., Comment: 31pages,15figures

We show that the multiplicity of the second normalized adjacency matrix eigenvalue of any connected graph of maximum degree $\Delta$ is bounded by $O(n \Delta^{7/5}/\log^{1/5-o(1)}n)$ for any $\Delta$, and by $O(n\log^{1/2}d/\log^{1/4-o(1)}n)$ for simple $d$-regular graphs when $d\ge \log^{1/4}n$. In fact, the same bounds hold for the number of eigenvalues in any interval of width $\lambda_2/\log_\Delta^{1-o(1)}n$ containing the second eigenvalue $\lambda_2$. The main ingredient in the proof is a polynomial (in $k$) lower bound on the typical support of a closed random walk of length $2k$ in any connected graph, which in turn relies on new lower bounds for the entries of the Perron eigenvector of submatrices of the normalized adjacency matrix., Comment: A previous version of this paper proved the main result for d-regular graphs. The current version proves a more general result for the normalized adjacency matrix of bounded degree graphs. New version fixes an incorrect citation in the proof of Proposition 5.2. 24pp, 3 figures

In this article, we analyze the limiting eigenvalue distribution (LED) of random geometric graphs (RGGs). The RGG is constructed by uniformly distributing $n$ nodes on the $d$-dimensional torus $\mathbb{T}^d \equiv [0, 1]^d$ and connecting two nodes if their $\ell_{p}$-distance, $p \in [1, \infty]$ is at most $r_{n}$. In particular, we study the LED of the adjacency matrix of RGGs in the connectivity regime, in which the average vertex degree scales as $\log\left( n\right)$ or faster, i.e., $\Omega \left(\log(n) \right)$. In the connectivity regime and under some conditions on the radius $r_{n}$, we show that the LED of the adjacency matrix of RGGs converges to the LED of the adjacency matrix of a deterministic geometric graph (DGG) with nodes in a grid as $n$ goes to infinity. Then, for $n$ finite, we use the structure of the DGG to approximate the eigenvalues of the adjacency matrix of the RGG and provide an upper bound for the approximation error.

In this paper, we continue our work on video relocalization task. Based on using graph convolution to extract intra-video and inter-video frame features, we improve the method by using similarity-metric based graph convolution, whose weighted adjacency matrix is achieved by calculating similarity metric between features of any two different time steps in the graph. Experiments on ActivityNet v1.2 and Thumos14 dataset show the effectiveness of this improvement, and it outperforms the state-of-the-art methods., Comment: arXiv admin note: substantial text overlap with arXiv:2007.09877

Minimal codewords have applications in decoding linear codes and in cryptography. We study the number of minimal codewords in binary linear codes that arise by appending a unit matrix to the adjacency matrix of a graph., Comment: 11 pages

We study the Wasserstein metric to measure distances between molecules represented by the atom index dependent adjacency "Coulomb" matrix, used in kernel ridge regression based supervised learning. Resulting quantum machine learning models exhibit improved training efficiency and result in smoother predictions of molecular distortions. We first demonstrate smoothness for the continuous extraction of an atom from some organic molecule. Learning curves, quantifying the decay of the atomization energy's prediction error as a function of training set size, have been obtained for tens of thousands of organic molecules drawn from the QM9 data set. In comparison to conventionally used metrics ($L_1$ and $L_2$ norm), our numerical results indicate systematic improvement in terms of learning curve off-set for random as well as sorted (by norms of row) atom indexing in Coulomb matrices. Our findings suggest that this metric corresponds to a favorable similarity measure which introduces index-invariance in any kernel based model relying on adjacency matrix representations.

The problem of decomposing a complete tripartite graph into 5-cycles was first proposed in 1995 by Mahmoodian and Mirzakhani and since then many attempts have been made to decompose such graphs into 5-cycles. Such attempts were partially successful but parts of the problem still remain open. In this paper, we investigate the problem deeper, decompose more tripartite graphs into 5-cycles, and introduce the Graph Adjacency Matrix (GAM) method for cycle decomposition in general. GAM method transforms the cycle decomposition problem to covering squares with certain polygons. This new formulation is easier to solve and enables us to find explicit decompositions for numerous cases that were not decomposed before., Comment: updated, 1 figure added

The Estrada topological index EE, based on the eigenvalues of the adjacency matrix, is degenerate for cospectral graphs. By additionally considering the eigenvectors, two new topological indices are devised (RV_a and RV_b), which have reduced degeneracy for alkanes or cyclic graphs. Index RV_a shows similarity to EE in ordering of alkanes with 8 to 10 carbon atoms, whereas index RV_b is more similar to the average distance-based connectivity (Balaban index J). Inter-correlations between these four topological indices are discussed, indicating which factors have predominant influence.

A complex unit gain graph is a simple graph in which each orientation of an edge is given a complex number with modulus 1 and its inverse is assigned to the opposite orientation of the edge. In this article, first we establish bounds for the eigenvalues of the complex unit gain graphs. Then we study some of the properties of the adjacency matrix of complex unit gain graph in connection with the characteristic and the permanental polynomials. Then we establish spectral properties of the adjacency matrices of complex unit gain graphs. In particular, using Perron-Frobenius theory, we establish a characterization for bipartite graphs in terms of the set of eigenvalues of gain graph and the set of eigenvalues of the underlying graph. Also, we derive an equivalent condition on the gain so that the eigenvalues of the gain graph and the eigenvalues of the underlying graph are the same., Comment: 14 pages, 2 figures