Enhancing Link Prediction with Fuzzy Graph Attention Networks and Dynamic Negative Sampling

A fuzzy information system is defined as a tuple $(U,A,V,f)$, where $U$ represents a non-empty finite set of samples, $A$ denotes the finite set of sample attributes, $V$ represents the domain of all attributes in $A$, expressed as $V=\bigcup_{i}V_{i}$ where $V_{i}$ is the domain of attribute $i$, and $f$ is a mapping function $U\times A\rightarrow V$ [11].

For an attribute set $B\subseteq A$ and a fuzzy equivalence relation $R$, we can compute a coverage of the universe $U$. For a sample $x$, we denote its coverage under the fuzzy equivalence relation $R$ as $[x]_{R}$. The membership of a sample $y$ to the coverage $[x]_{R}$ is defined as $[x]_{R}(y)=R(x,y)$, where $R(x,y)$ quantifies the similarity between samples $x$ and $y$ under relation $R$. For any sample $x\in U$ and subset $X\subseteq A$, the fuzzy lower and upper approximations of sample $x$ to $X$ are defined as [11]:

where $S$ and $T$ represent fuzzy triangular conorm (S-norm) and fuzzy triangular norm (T-norm) respectively, and $N(x)=1-x$.

Using the conventional min-max version of $T$ and $S$ norms, for a set of samples $d_{i}$ of class $i$ and corresponding attribute set $B\subseteq A$, Equation 1 can be reformulated as:

To capture non-linear high-level similarities, $R$ typically employs kernel functions, including the Gaussian kernel: $k_{G}(x,y)=\exp(-\frac{||x-y||^{2}}{\delta})$, exponential kernel: $k_{E}(x,y)=\exp(-\frac{||x-y||}{\delta})$, and rational quadratic kernel: $k_{R}(x,y)=1-\frac{||x-y||^{2}}{||x-y||^{2}+\delta}$.

During each training epoch, negative links are dynamically selected based on their quality scores. For any potential negative link with end nodes $(x,y)$, the quality score is computed as:

where $\alpha$ is a hyperparameter.

While computing quality scores for all possible negative edges and selecting the top k would be optimal, this approach becomes computationally intractable for large dense graphs. For a graph with $N$ nodes and $E$ edges, there exist $N\times(N-1)-E$ potential directed negative edges. To address this computational challenge, we randomly select $2E$ negative edges and select the top $E$ edges among them. This strategy reduces the computational complexity from $N\times(N-1)-E$ to $2E$ while maintaining near-optimal performance.

The selected top $E$ negative edges are combined with the original positive edges to form the training dataset. To prevent class imbalance issues, we maintain an equal number of selected negative edges and original positive edges.

The FGAT convolution layer integrates GAT convolution layers with linear layers, incorporating layer normalization for training acceleration and dropout mechanisms for effective regularization.

Given an undirected graph $G=(V,E)$, where $V$ represents the set of nodes and $E$ denotes the set of edges, each node $v\in V$ is associated with a feature vector $\mathbf{h}_{v}\in\mathbb{R}^{F}$, where $F$ represents the dimension of input features per node. The FGAT layer aims to compute updated node representations $\mathbf{h}_{v}^{\prime}\in\mathbb{R}^{F^{\prime}}$, where $F^{\prime}$ denotes the output feature dimension, by performing weighted aggregation of features from each node’s neighborhood.

For a node pair consisting of node $v$ and its neighbor $u$, the attention coefficient $e_{vu}$ is computed through:

where:

• •

  $\mathbf{W}\in\mathbb{R}^{F^{\prime}\times F}$ represents a learnable weight matrix that transforms node features linearly.

• •

  $\parallel$ indicates vector concatenation.

• •

  $\mathbf{a}\in\mathbb{R}^{2F^{\prime}}$ denotes a learnable weight vector.

• •

  LeakyReLU serves as the activation function, typically configured with a small negative slope (e.g., 0.2).

The attention coefficients then undergo normalization across each node’s neighborhood using the softmax function:

where $\mathcal{N}(v)$ represents the neighborhood set of node $v$.

The normalized attention scores $\alpha_{vu}$ facilitate the computation of updated node features $\mathbf{h}_{v}^{\prime}$ through weighted aggregation:

where $\sigma$ represents a non-linear activation function, typically implemented as ReLU.

To enhance model robustness and representational capacity, the GAT layers employ multi-head attention mechanisms. Specifically, K independent attention heads operate in parallel, each generating distinct attention coefficients and feature representations. These representations are subsequently concatenated to produce the final output:

where $\alpha_{vu}^{(k)}$ and $\mathbf{W}^{(k)}$ correspond to the attention coefficient and weight matrix of the k-th attention head, respectively.

Layer normalization [21] is incorporated to stabilize and expedite the training process by normalizing layer inputs. For an input vector $\mathbf{h}=[h_{1},h_{2},\dots,h_{d}]$ with $d$ features, the normalized output $\mathbf{\hat{h}}=[\hat{h}_{1},\hat{h}_{2},\dots,\hat{h}_{d}]$ is computed as:

where $\mu=\frac{1}{d}\sum_{i=1}^{d}h_{i}$ represents the mean, $\sigma^{2}=\frac{1}{d}\sum_{i=1}^{d}(h_{i}-\mu)^{2}$ denotes the variance, and $\epsilon$ is a small constant ensuring numerical stability. The final output $y$ is obtained through the application of learnable scaling parameter $\gamma$ and bias term $\beta$:

As illustrated in Figure 1, the FGAT framework operates through a systematic process that begins with dynamic negative edge selection during each training epoch, utilizing the given adjacency matrix. These dynamically selected negative edges, along with the existing positive edges, are subsequently processed by the FGAT layer in conjunction with their corresponding node embeddings. To effectively capture long-range dependencies within the graph structure, multiple FGAT layers are cascaded, with residual connections implemented to enhance training stability and information flow. Following the iterative processing through these layers, we obtain updated node representations $H=\{h_{1},h_{2},\dots,h_{N}\}$. The probability of link existence between any pair of nodes $x$ and $y$ is then computed as:

The framework’s effectiveness stems from two key components: the fuzzy negative sampling technique, which efficiently identifies and selects high-quality negative edges, and the FGAT layer architecture, which performs iterative neighbor information aggregation. The empirical validation of this framework’s performance is documented in the experiments section, demonstrating its effectiveness in link prediction tasks.

Our evaluation utilizes two research collaboration network datasets, summarized in Table I.

The Ca-netscience dataset comprises 379 nodes and 914 edges, with an average node degree of 2.4. In contrast, Ca-sandi-auths exhibits a more sparse structure with fewer nodes, edges, and a lower average node degree. Both datasets are directed networks. For experimental purposes, we employ a 70-10-20 split ratio, where 70% of the data is used for training, 10% for validation (early stopping), and 20% for testing.

We benchmark FGAT against several prominent baseline models: MLP, GCN [3], GraphSAGE [1], and GAT [2]. All baseline models maintain their default parameter configurations. For FGAT implementation, we configure the embedding dimension to 128 and employ a stack of 4 FGAT convolution layers. The dataset partitioning follows the aforementioned 0.7:0.1:0.2 ratio for training, validation, and testing, respectively.

To ensure a comprehensive performance assessment, we employ multiple evaluation metrics: Precision, Recall, F1 score, and ROC score. This diverse set of metrics provides a multifaceted evaluation, enabling thorough analysis of each model’s capabilities across different performance aspects.

The experimental results are presented in Table II, yielding several significant observations:

• •

  On the Ca-netscience dataset, MLP demonstrates the poorest performance, attributable to its inability to capture spatial information encoded in the adjacency matrix. GCN, GraphSAGE, and GAT exhibit comparable performance levels, with GraphSAGE achieving superior Recall scores and GAT excelling in F1 metrics. For the Ca-sandi-auths dataset, MLP achieves notable Recall but relatively inferior Precision, suggesting overfitting tendencies and limited generalization capability. GAT, leveraging its attention mechanism, achieves the highest ROC scores among baseline methods.

• •

  FGAT outperforms baseline methods across both datasets in terms of the average of four evaluation metrics. Specifically, it demonstrates an average improvement of 7.11% across all metrics on Ca-netscience, and a more substantial 15.55% improvement on Ca-sandi-auths. This superior performance can be attributed to two key factors: the fuzzy negative sampling mechanism, which enables focused learning on error-prone edges, and the FGAT layer architecture, which provides robust message aggregation capabilities.