GraphMinNet: Learning Dependencies in Graphs with Light Complexity Minimal Architecture

GRU has been improved to minGRU (Feng et al., 2024) to overcome gradient vanishing/explosion and enable better capture of global dependencies. For an input sequence of tokens, minGRU is defined as:

where $x_{t}\in\mathbb{R}^{d_{x}}$ is the input feature vector and $h_{t}\in\mathbb{R}^{d_{h}}$ is its corresponding state-space representation at time $t$. Here, $\sigma(\cdot)$ is an element-wise non-linear activation function with values in $(0,1)$, and $\text{Linear}_{d_{h}}(x_{t})$ projects $x_{t}$ to a $d_{h}$-dimensional state space via an MLP.

The model achieves computational efficiency with complexity $O(2d_{x}d_{h})$ (Feng et al., 2024), significantly lower than the original GRU’s $O(3d_{h}(d_{x}+d_{h}))$. Training can be parallelized using a parallel scan algorithm (Feng et al., 2024). To enable more effective feature extraction, minGRU employs state expansion where the state dimension $d_{h}=\alpha d_{x}$ with $\alpha\geq 1$.

The minGRU model enhances the original GRU with several key advantages: 1) ability to capture global dependency, 2) linear efficiency in terms of input sequence length, 3) scalable model size with respect to input length, and 4) shift equivariance. Moreover, compared to state-space models (Gu et al., 2020) (Gu et al., 2021), in particular, Mamba (Gu & Dao, 2023) that has a linear complexity and scalability, minGRU does not have a fixed state-space length and thus have a stronger ability to possess context awareness or content selectivity (Feng et al., 2024). These advantages offer potential solutions to common GNN challenges, motivating our development of GraphMinNet.

To develop this model, first we obtain the explicit expression of the minGRU model containing no state variable $h_{t}$:

In the last equality of Eq. (2) and hereafter, the notation $\prod$ stands for element-wise multiplication of $d_{h}$-dimensional vectors across relevant indexes. By denoting $c_{i}=\prod_{j=1}^{i}(1-z_{j})$, $i=1,\cdots,t$, Eq. (2) can be written as

The above equation can facilitate us to derive a corresponding model for graph learning, as it does not contain any intermediate, latent state variables.

For a graph $G=(V,A)$ with $n$ nodes in set $V$ and adjacency matrix $A$, each node $u$ has a feature vector $x_{u}\in\mathcal{R}^{l}$. To introduce the idea of minGRU to graph-structured data, we make three key observations:

1) Position Indexing: While minGRU uses sequence positions as indices, we associate these with graph nodes. Since graphs lack natural ordering, we replace $\sum_{i\leq t}$ with $\sum_{v\in V}$ to ensure permutation equivariance.

2) Positional Information: To capture node positions in the graph structure, we employ Laplacian positional embedding (LPE) (Wang et al., 2022; Huang et al., 2024b, 2023). Given the graph Laplacian eigendecomposition $L=\tilde{V}\Lambda\tilde{V}^{T}$, where $\tilde{V}\in{\mathcal{R}^{n\times n}}$ contains the eigenvectors and $\Lambda$ is the diagonal eigenvalue matrix, we define the $d$-dimensional LPE for node $u$ as $p_{u}=\tilde{V}[u,1:d]\in{\mathcal{R}^{d}}$. This encoding captures the absolute position of node $u$ in the graph. We denote by $\Lambda_{d}$ the vector of top $d$ non-zero eigenvalues.

3) Content Dependence: The interaction terms $c_{i}^{-1}\odot c_{t}$ depend on $z_{j}$ (for $i+1\leq j\leq t$), which in turn depend on input features $x_{j}$, creating content-dependent state variables. This mechanism parallels the selection mechanism in Mamba (Gu & Dao, 2023; Ahamed & Cheng, 2024). To fully capture both structural and feature information, we encode positions and features separately in matrix form. Therefore, we need to replace the $\odot$ operation involving the matrices with suitable operations that produce vectors.

Based on these observations, we construct the node embedding as follows. First, we define the feature component $A_{u}\in\mathcal{R}^{d\times m}$ for node $u$:

where $W\in\mathcal{R}^{d\times l}$ is a learnable weight matrix and $\phi_{i}(\cdot):\mathcal{R}^{d}\rightarrow\mathcal{R}^{d}$ are learnable permutation equivariant functions, $i=1,\cdots,m$. Here, $\phi_{i}(\Lambda_{d})$ are permutation equivariant to the top-$d$ eigenvalues of the Laplacian, similar to the global permutation-equivariant set aggregation functions in (Wang et al., 2022; Huang et al., 2024b).

Similarly, we construct the positional component $C_{u}\in\mathcal{R}^{d\times m}$:

The overall embedding for node $u$ combines these components:

where $B\in\mathcal{R}^{l\times d}$ is a learnable matrix and $\oplus_{1}$ denotes element-wise aggregation (e.g., addition or multiplication) between matrices $A_{u}$ and $C_{u}$. The resulting embedding $a_{u}$ has size $l\times m$.

The inverse operation in minGRU is adapted to graphs by associating node encodings with quantities in Eq. (2) and Eq. (3): $a_{v}\leftarrow c_{j}^{-1}\odot z_{j}\odot\tilde{h}_{j}$ for any node $v\in V$ and $a_{v}\odot z_{v}\odot\tilde{h}_{v}\leftarrow c_{j}$, where $\odot$ between $a_{v}$ and $z_{v}$ denotes element-wise multiplication of each column of $a_{v}$ with $z_{v}$.

Inspired by Eq. (3), we formulate GraphMinNet for node $u$ as:

Here, the state variable $h_{u}$ has the same dimension $l$ as node feature $x_{u}$. Our formulation differs from the graph convolution in (Huang et al., 2024b) in two key aspects: First, nonlinear feature dependence where $h_{u}$ depends nonlinearly on $x_{u}$ through $\tilde{h}_{u}$ (linear transformation), $z_{u}$ (gated feature attention), and $A_{u}$ (in $a_{u}$, containing $x_{u}$ in each column), with the gated feature attention providing automatic focus on important features. Second, while (Huang et al., 2024b) primarily emphasizes positional encoding, our formulation incorporates features through $A_{u}$, $z_{u}$, and $\tilde{h}_{u}$.

For matrix $a_{v}$, the $\odot$ operation with vector $z_{v}\odot\tilde{h}_{v}$ multiplies the vector element-wise with each matrix column. Defining $\bar{a}=\sum_{v\in V}a_{v}$, we can reformulate Eq. (7) as:

Here, we generalize the $\odot$ operation between $a_{u}$ and $\bar{a}$ by an inner product operation $\langle\cdot,\cdot\rangle$ because $a_{u}$ and $\bar{a}$ are matrices. As $\bar{a}=\sum_{v\in V}a_{v}$, we define $\langle a_{u},a_{v}\rangle$ using four types of inner products:

Type 1. Elementary inner product between corresponding matrix rows;

Type 2. For $m=l$, elementary inner product between corresponding columns, followed by transposition into a column-vector;

Type 3. Inner product of vectorized matrices, with result multiplied by $l$-dimensional all-ones vector;

Type 4. Either $\langle BC_{u},BC_{v}\rangle\langle A_{u},A_{v}\rangle$ or $\langle BA_{u},BA_{v}\rangle$ $\langle C_{u},C_{v}\rangle$, where the first inner product uses any of Types 1-3 and the second uses Type 2 or 3.

Note that the Einstein summation operation (einsum) in torch can be used to efficiently calculate these different types of products. In the model, all nodes $v$ share the same weight matrices $B$ (in $a_{v}$) and $W$ (in $A_{v}$). Because emphasizing on node $u$ potentially facilitates capturing its useful information, we may further consider the following formulation:

where $\beta\in[0,2]$ is a weighting parameter, $W_{s1},W_{s2}\in\mathcal{R}^{d\times d}$ are learnable matrices, and $1_{l}\in\mathcal{R}^{l}$ is an all-ones vector. The inner product $\langle\cdot,\cdot\rangle$ in the second term uses Type 3 (matrix vectorization). This formulation generalizes Eq. (7), which can be recovered as a special case when $\beta=1$, showing how the self-loop term integrates with the original structure.

We present several key properties of our GraphMinNet formulation. Detailed proofs are provided in the appendix.

This property ensures that when nodes of an input graph are reordered (permuted), the node-level outputs transform according to the same permutation. Since node ordering in graphs is arbitrary, permutation equivariance provides an essential inductive bias that enables the model to learn representations independent of node indexing.

Stability encompasses three aspects: Structural stability refers to how outputs change when edges are added/removed. Thus, it is about what the output response is to changes in graph connectivity. Feature stability refers to how outputs change when node/edge features are perturbed, thus is about sensitivity to noise in feature values. Spectral stability refers to how changes in the graph’s eigenvalues affect the output, which is particularly important for spectral-based GNN approaches. As shown in (Huang et al., 2023), stability is more general than equivariance (Huang et al., 2023) and implies generalization ability (Bousquet & Elisseeff, 2002) (Shalev-Shwartz et al., 2010). Therefore, the stability property is critical to the GNN algorithm’s robustness to noise in real-world data, generalization abilities, and adversarial robustness.

Many common permutation equivariant functions in neural networks are naturally Lipschitz, including linear permutation equivariant functions, element-wise Lipschitz operations, max/min pooling, and mean pooling. Thus, the Lipschitz condition is readily satisfied for typical choices of $\phi(\cdot)$, ensuring provable stability of GraphMinNet. As stability implies strong generalizability and robustness, we have the following result.

The following property establishes GraphMinNet’s ability to capture long-range dependencies, which is critical for effective graph learning.

In this paper, we assume the eigenvalue decomposition of $A$ is pre-computed. For large sparse graphs, we adopt the Lanczos algorithm (e.g., implemented in ARPACK) to efficiently compute the $d$ largest/smallest eigenvalues and eigenvectors of the adjacency/Laplacian matrices. This computation has complexity $O(Md)$, where $M$ is the number of edges. Given these pre-computed eigenvalues and eigenvectors, the complexity and scalability of our algorithm is given as follows:

These properties collectively demonstrate that GraphMinNet achieves efficient long-range dependency modeling with linear complexity while maintaining strong expressive power between 1-WL and 3-WL tests.

To validate our theoretical stability results empirically, we evaluate our method’s robustness to feature perturbations. We introduce controlled synthetic noise to node embeddings by adding Gaussian perturbations proportional to the feature magnitudes. For each node $x_{u}\in\mathbb{R}^{l}$, we compute the perturbed embedding $x^{\prime}_{u}$ as:

where $\epsilon$ is the noise level, and $n_{u}\in{\mathcal{R}}^{l}$ is a noise term. We consider two types of noise: additive white noise $n_{u}=\mathcal{N}(0,I)$ and signal-dependent noise $n_{u}=\mathcal{N}(0,I)\odot\mu(x)$. Here, $\mathcal{N}(0,I)$ is standard multivariate Gaussian, and $\mu(x)$ denotes the mean feature magnitude. The second type models perturbations that scale appropriately with the underlying feature values. Figure 4 shows our method’s performance on Molhiv and Peptides-Func datasets under increasing noise levels (0%, 5%, …, 30%). The results demonstrate consistent performance across noise levels, empirically confirming our theoretical stability guarantees.

We first investigate the impact of the self-term introduced in Eq. (11). Results in Table 3 show dataset-dependent effects: while the self-term improves performance on Molhiv (AUROC increase of 2.55%), it slightly decreases performance on CLUSTER and Peptides-func. This variation suggests the self-term’s effectiveness correlates with specific graph properties - it appears more beneficial for molecular graphs with complex local structures (like Molhiv) compared to more regular graph structures (like CLUSTER).

We analyzed different methods for aggregating node embeddings $a_{u}$ in Eq. 6, comparing two element-wise operations for combining feature and positional information: multiplication and addition. Our results showed that element-wise multiplication achieves higher accuracy across most datasets (e.g., two datasets shown in Table 4). Based on these results, we adopt element-wise multiplication by default except for MalNet-Tiny, which uses element-wise addition.

We analyze the impact of dropout regularization on model performance. Figure 5 compares training and validation performance with and without dropout. The results demonstrate that dropout plays a crucial role in preventing overfitting - models without dropout show significant performance degradation on validation sets, particularly on complex datasets like Peptides-func and Molhiv. This confirms dropout’s importance as a regularization mechanism in our architecture.

We evaluate GraphMinNet’s stability when combined with different local methods that use local neighborhood information including edge features, such as GatedGCN and GINE. Table 5 shows that GraphMinNet maintains consistent performance across different local methods: performance variations remain within about $2\%$ on CLUSTER, $0.6\%$ on Peptides-func, and within about $0.6\%$ on Molhiv. These minimal differences across diverse datasets demonstrate that GraphMinNet can effectively integrate local structural information regardless of the specific local method employed, confirming its architectural robustness and versatility.

In our method, we utilized single layer linear transformation for matrix $W$ and $B$. However, to explore further, instead of only using linear projection, we perform ablation study with two linear layers and a nonlinear activation such as ReLU/GELU/SiLU in between in both $W$ and $B$ matrix. We report the results in Table 6. From this, we can see that, for Molhiv and CLUSTER, the performance variation is around $1\%$. However, for Peptides-func, performance drops around $7\%$. Therefore increasing more layers may lead to overfitting performance for graph data. Particularly for smaller datasets like Peptides-func.

Inspired by minGRU (Feng et al., 2024), we adopt a linear projection (LP) for both $z_{u}$ and $\tilde{h}_{u}$ in our method. However, to further explore the projection strategy, we conduct an ablation study by employing a nonlinear projection (NLP), similar to Subsection 5.5. The results presented in Table 7 indicate that NLP maintains competitive performance and may be beneficial for datasets with higher-dimensional node features to capture complex patterns. However, since NLP does not provide significant improvements while introducing additional parameters, we adopt LP as the default projection strategy for all datasets.

Assuming that the eigenvalue decomposition of the adjacent matrix $A$ is precomputed and thus given, we have the following computational complexity for GraphMinNet:

The above property provides a certificate guaranteeing the linear complexity as well as the linear scalability with respect to the number of nodes of the graph.