REGE: A Method for Incorporating Uncertainty in Graph Embeddings

arXiv:2412.05735 · cs.LG · Submitted 2024-12-07 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Hi, I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "REGE: A Method for Incorporating Uncertainty in Graph Embeddings".

Jane: Here's the gist of the paper. The gist REGE introduces an approach that measures and incorporates uncertainty in data and model outputs to produce graph embeddings with radius values representing the uncertainty of the model’s output, which improves accuracy under adversarial attacks.

Tom: Data Uncertainty Definition The authors define uncertainty in graph data using low-rank representations of the graph G to produce multiple instances of it: "We use the low-rank representation of the graph G to produce multiple instances of it" (Page 1).

Jane: They find this by calculating the eigen-decomposition and reconstructing a sequence of graphs using various low-rank representations, which are then sent to a consensus function that calculates uncertainty associated with the presence or absence of edges in G ∪ its reconstructions, outputting a weighted adjacency matrix W (Page 1).

Tom: The uncertainty for an edge is computed using a binary deviation function: "ue = 1 − Wij − (1 − Wij)" (Page 3).

Title and authors: Tom: Let's look at the title and the authors of this paper, "REGE: A Method for Incorporating Uncertainty in Graph Embeddings." The title itself is pretty descriptive—it immediately tells you what the method is about.

Jane: It points out that the core idea is incorporating uncertainty into graph embeddings. So, we're talking about moving beyond just getting a single embedding vector and recognizing that there's a range of possibilities for where that node actually belongs in the embedding space.

Lu: The authors are Shafi, Savcisens, and Eliassi-Rad from Northeastern University Boston. They’re researchers in the field of machine learning for graphs.

Meng: So, what does it mean when they say they are incorporating uncertainty? Does that mean their embeddings won't be as precise? I mean, precision is important for deploying models to production environments where we need consistent results.

Tom: Not necessarily less precise; it means the embeddings come with a measure of confidence. They produce graph embeddings with radius values that represent the uncertainty of the model’s output, which is a direct way of quantifying that uncertainty.

Jane: So, instead of just giving us one number for a node's embedding, we get two things: the embedding itself and a radius value that tells us how much we should trust it.

Lu: They tackle this by using curriculum learning for data uncertainty and conformal learning to address the model-dependent uncertainty in the output. That’s a sophisticated way to handle both sources of noise.

Meng: I’m curious about the complexity of those techniques. Are these just extra layers on top, or is this fundamentally changing how we think about training graph embedding functions?

Tom: It's more of a structured approach than just adding layers. They use the eigen-decomposition to create multiple graph views, and then use those views to calculate data-dependent radii using a consensus function and binary deviation function.

Jane: So they are essentially using different ways to look at the same graph structure—reconstructing it in different ways—to see where the edges might be missing or noisy.

Lu: And that process gives them the weighted adjacency matrix W, and then they use that matrix to calculate a radius for each node by aggregating those edge uncertainties.

Meng: So, if we think about this from an engineering standpoint, it sounds like they are doing a lot of work upfront just to characterize the graph's inherent noise before even starting the main embedding task.

Tom: That’s right. They generate these data-dependent radii, or DDRs, and then they use them to inject noise into the hidden layer representations of each node, sampled from a normal distribution with a mean of zero and a variance equal to that node's radius.

Jane: And that noise injection is the mechanism that forces the model to learn robust representations for those nodes based on their measured structural uncertainty.

Lu: And then they add the model-dependent radii, MDRs, which come from that student-teacher setup with quantile loss and conformal learning, giving them a full picture of uncertainty.

Meng: So we’re looking at a very comprehensive framework that measures data noise, model error, and then uses those measurements to guide the training process through curriculum learning on graph views.

The paper's summary: Tom: So, summarizing the REGE paper, they introduce Radius Enhanced Graph Embeddings. The main thing is that it measures and incorporates uncertainty in data to create embeddings with radius values that represent how uncertain the model’s output is.

Jane: That means we are not just getting a single embedding anymore; we get an embedding plus a radius value for each node, which directly representing the uncertainty surrounding that node's mapping.

Lu: They use two main components: data-dependent radii to quantify uncertainty based on low-rank representations of the graph G and then model-dependent radii derived from a student-teacher model using quantile loss and conformal learning.

Meng: So, it’s a dual approach—one side looking at the structure of the graph, and the other side looking at how uncertain our current AI is about producing a specific embedding in space.

Tom: And then they use these radii to inject noise proportional to their values into the hidden layer representations during training, which forces nodes with higher variances to have less stable embeddings.

Jane: It’s a way of saying that if the data structure around a node is highly uncertain, or if our current model is unsure about its output, we should train it to be more robust for that uncertainty.

Lu: The curriculum learning helps improve accuracy under adversarial attacks by training the graph embedding function sequentially on graphs reconstructed with increasing numbers of components.

Meng: And they claim this method outperforms competing methods by an average of one point five percent in accuracy against state-of-the-art methods when tested on Cora, Citeseer, and PolBlogs <ref:2412.05735#pg1,accuracy against state-of-the-art methods>. That’s a solid performance metric under adversarial conditions.

Tom: So the main thing to remember is that REGE provides graph embeddings that are more robust under adversarial attacks because it systematically measures and incorporates both data uncertainty and model output uncertainty into the training stage.

Jane: It's a method for building trust into these graph embeddings by explicitly modeling the uncertainty, rather than just hoping our embedding is good enough.

The paper's improvements: Tom: They suggest two main things as improvements: first, quantifying data uncertainty with DDRs using eigen-decomposition and a consensus function to derive the weighted adjacency matrix W, which then yields node radii ri.

Jane: And second, quantifying model uncertainty using a student-teacher model where the student predicts alpha-quantiles and (one-alpha) -quantiles for each dimension of z u, with those quantiles refined by conformal learning to give them the MDRs <ref:2412.05735#pg1>.

Lu: And then they incorporate both DDRs and MDRs by injecting noise into the hidden layer representations of each node, where the noise is sampled from a normal distribution with a mean of zero and a variance equal to the node's radius.

Meng: That noise injection is key because it ensures that nodes with higher variances exhibit less stable embeddings, which means we need to know how this scales when we are running this on real traffic.

Tom: And they use curriculum learning on graph views derived from eigen-decomposition for training the embedding function, starting from the most simplified version.

Jane: That curriculum learning is crucial because it builds up robustness at each stage of the process, showing that sequential training improves performance under adversarial attacks.

Lu: They also point out that their binary deviation function for DDRs allows low-degree nodes to have low radii, which captures more information than just degree distribution.

Meng: So they are claiming this is a better way to capture the underlying structural uncertainty than just relying on standard measures like standard deviation or entropy for these types of measures.

Tom: They also state that REGE consistently achieves higher accuracy at lower number of components used in their curriculum learning process, which is efficient in terms of how much complexity they need to learn.

Jane: So the improvement isn't just about adding more layers; it’s about having a more principled way to measure and control the instability we are introducing during training through these specific noise injections.

Conclusion: Tom: So, wrapping up on "REGE: A Method for Incorporating Uncertainty in Graph Embeddings." The main thing is that REGE successfully incorporates both data and model uncertainty into the training stage by systematically measuring them through eigen-decomposition and student-teacher models.

Jane: It leads to graph embeddings that are more robust against adversarial attacks, with an average one point five percent accuracy improvement over state-of-the-art methods on Cora, Citeseer, and PolBlogs datasets <ref:2412.05735#pg1,state-of-the-art methods>.

Lu: The implication is that we can build systems where we have a way to explicitly model the uncertainty around the embedding output before deployment.

Meng: For production, that means our monitoring needs to track those radii because if they spike, it’s a warning sign about structural instability in the underlying data distribution.

Tom: So REGE is about making sure the AI doesn't just produce a number, but that number is backed by some kind of quantified confidence.

Jane: It’s about building trust into these graph embeddings through this systematic approach to modeling both data and model uncertainty, and it’s a really valuable piece of work for anyone working in this area.

Lu: I think the way they do it—separating the data uncertainty from the model uncertainty is what makes this method powerful because it lets you address each source individually.

Meng: It’s definitely more than just a quick fix; it’s a deep architectural change that forces us to consider these uncertainties as first-class citizens in our design.

Tom: So we're done with this paper on REGE for now, but I think the next time you hear about graph embeddings, you should keep an ear out for methods that are doing this kind of uncertainty modeling.

Zohair Shafi, Germans Savcisens, Tina Eliassi-Rad

Northeastern University

cs.LG

Submitted: 2024-12-07

Updated: 2024-12-07

Journal ref: Proceedings of the 2025 SIAM International Conference on Data Mining (SDM), pp. 376-385

DOI: 10.1137/1.9781611978520.40

Code: https://github.com/zohairshafi/REGE

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: The gist REGE introduces an approach that measures and incorporates uncertainty in data and model outputs to produce graph embeddings with radius values representing the uncertainty of the model’s

Key concepts

Data-Dependent Radii (DDR): This measures how uncertain the graph structure is. It is calculated by using low-rank representations of the graph to create multiple versions, then a consensus function determines edge uncertainty in these versions. These uncertainties are aggregated to produce a radius for each node based on its incident edges.
Model-Dependent Radii (MDR): This quantifies the uncertainty in the model's output embedding. It uses a student-teacher setup where a teacher produces an embedding, and a student MLP predicts quantile intervals. Conformal learning then refines these predictions, and the average distance between these predicted quantiles defines the node's radius.
Radius Noise Injection: The calculated data and model radii are used to inject controlled noise into the hidden layers of each node during training. This noise is sampled from a normal distribution whose variance matches the node's radius, forcing the model to learn stable representations for nodes with higher inherent uncertainty.
Curriculum Learning: The training process uses curriculum learning on graph views derived from eigen-decomposition. The model is trained sequentially on these views, starting with simpler versions and gradually introducing more components. This gradual complexity helps the model build robust embeddings that perform better under adversarial attacks.

Terminology

Embeddings — 4× in this paper · explained in 2 episodes
Accuracy — 1× in this paper · explained in 1 episode
Curriculum Learning — 1× in this paper · explained in 3 episodes
Radius Enhanced Graph Embeddings — 1× in this paper

Summary

The gist REGE introduces an approach that measures and incorporates uncertainty in data and model outputs to produce graph embeddings with radius values representing the uncertainty of the model’s output, which improves accuracy under adversarial attacks.

Data Uncertainty Definition

The authors define uncertainty in graph data using low-rank representations of the graph G to produce multiple instances of it: We use the low-rank representation of the graph G to produce multiple instances of it (Page 1). They find this by calculating the eigen-decomposition and reconstructing a sequence of graphs using various low-rank representations, which are then sent to a consensus function that calculates uncertainty associated with the presence or absence of edges in G ∪ its reconstructions, outputting a weighted adjacency matrix W (Page 1). The uncertainty for an edge is computed using a binary deviation function: ue = 1 − Wij − (1 − Wij) (Page 3). Finally, the radius ri for a node i is calculated by averaging the uncertainty of the edges incident on that node: The radius ri for a node i is then calculated by averaging the uncertainty of the edges incident on the node (Page 3).

Model Uncertainty Definition

Uncertainty in model output is defined using a student-teacher model where a teacher produces an embedding Z, and a student MLP learns to predict α-quantiles and (1 − α)-quantiles for each dimension of zu (Page 1). Subsequently, the student's prediction is refined by a conformal learning algorithm: The trained MLP is called the student. The student learns to predict α-quantiles and (1 − α)-quantiles for each dimension of zu (Page 1). The distance between these quantiles averaged across all dimensions is defined as the distance between the quantiles averaged across all dimensions is our definition of uncertainty in the graph embedding function’s output (Page 1).

Incorporating Uncertainties into Training

The data-dependent radii (DDR) and model-dependent radii (MDR) are incorporated by injecting noise into the hidden layer representations of each node proportional to the node’s radius: We inject noise into the hidden representation of each node proportional to the uncertainty values (Page 1). This noise is sampled from a normal distribution with a mean of zero and a variance equal to the node’s radius, ensuring that nodes with higher variances exhibit less stable embeddings: The noise is sampled from a normal distribution with a mean of zero and a variance equal to the node’s radius (Page 3). The training procedure utilizes curriculum learning on the graph views: We then use curriculum learning [8] on the graphs G∪(G1, G2, G3,...) The curriculum learning improves the accuracy of the model under adversarial attacks (Page 2).

REGE Pipeline Components

The REGE pipeline involves several key steps:

Computing Data-Dependent Radii (DDR) using eigen-decomposition and a consensus function to derive the weighted adjacency matrix W, which then yields node radii ri: Algorithm 1 Generate Radius Values from eigendecomposition (Page 4).
Calculating Model-Dependent Radii (MDR) by utilizing a student-teacher model with conformal learning to estimate uncertainty across embedding dimensions: REGE uses conformal learning [7], a method that provides statistically rigorous prediction intervals (Page 5).
Incorporating these radii by perturbing the hidden layer representations of each node with noise sampled from a normal distribution whose variance equals the node’s radius: for each node i, radius ri and hidden layer representation x l i at layer l, we update Algorithm 2 Training GCN with Curriculum Learning and Radius Noise (Page 3).
Training the Graph Embedding Function using curriculum learning on a sequence of reconstructed graphs derived from eigen-decomposition: The curriculum training process, we train the model sequentially on these graph views, starting with the most simplified version (Page 3).

Experimental Results

Experiments evaluate REGE against eight defense methods on Cora [22], Citeseer [23], and PolBlogs [18] datasets under targeted availability attacks such as MinMax, Meta-Attack, and GraD: We use three well-known non-targeted availability attacks on graph structure: MinMax [9], Meta-Attack [10] and GraD [11] (Page 6). The results show that REGE outperforms competing methods by an average of 1.5% in accuracy against state-of-the-art methods: REGE’s graph embeddings perform better under adversarial attacks by an average of 1.5% (accuracy) against state-of-the-art methods (Page 1). Furthermore, REGE consistently outperforms competing methods across perturbation ranges, as shown in Table 5 for CoraML: REGE (D) and REGE-M consistently outperform competing methods (Page 13).

Conclusion

REGE successfully incorporates both data and model uncertainty into the training stage by systematically measuring them through eigen-decomposition and student-teacher models, leading to graph embeddings that are more robust against adversarial attacks. The method demonstrates superior performance compared to existing state-of-the-art techniques in defending against structural perturbations. REGE achieves higher accuracy at lower number of components used, indicating efficiency in the curriculum learning process: REGE consistently achieves higher accuracy at lower number of components used (Page 16).

--- Page 1 ---

REGE: A Method for Incorporating Uncertainty in Graph Embeddings Zohair Shafi∗ Northeastern University Boston, MA, U.S.A. Germans Savcisens† Northeastern University Boston, MA, U.S.A. Tina Eliassi-Rad‡ Northeastern University Boston, MA, U.S.A. Abstract Machine learning models for graphs in real-world applications are prone to two primary types of uncertainty: (1) those that arise from incomplete and noisy data and (2) those that arise from uncertainty of the model in its output; These sources of uncertainty are not mutually exclusive; Additionally, models are susceptible to targeted adversarial attacks, which exacerbate both of these uncertainties; In this work, we introduce Radius Enhanced Graph Embeddings (REGE), an approach that measures and incorporates uncertainty in data to produce graph embeddings with radius values that represent the uncertainty of the model’s output; REGE employs curriculum learning to incorporate data uncertainty and conformal learning to address the uncertainty in the model’s output; In our experiments, we show that REGE’s graph embeddings perform better under adversarial attacks by an average of 1.5% (accuracy) against state-of-the-art methods. 1 Introduction A graph embedding function, f, takes a graph G = (V, E) with n nodes, a node-attribute matrix X ∈ R n×f produces an embedding matrix Z ∈ R n×d; These embedding functions are useful in graph machine learning tasks such as node classification and link prediction and span various domains from financial systems [1] to biological networks [2, 3] to social media analysis [4]; A shortcoming of existing graph embedding functions is as follows: They do not capture the uncertainty that comes with incomplete and noisy graph data and/or the uncertainty that comes with the output of a model; For example (in the latter case), can we guarantee that a given node u in a graph G maps exactly to ⃗zu in a given d-dimensional space?; We conjecture that REGE takes an existing graph embedding function and incorporates such uncertainties into the training stage, thereby generating an embedding ⃗zu for each node u as well as a radius value ru representing the uncertainty around the node’s embedding; We further show that incorporating these uncertainties improves the accuracy of graph embeddings under adversarial attacks. How do we define uncertainty in the graph data? We use the low-rank representation of the graph G to produce multiple instances of it: We use the low-rank representation of the graph G to produce multiple instances of it (Page 1). To do so, we find the eigen-decomposition of G; We then reconstruct a sequence of graphs using various low-rank representations of the original graph G; Next, we send the generated graph sequence, along with the original G, to a consensus function that calculates the consensus in the presence/absence of edges in G ∪ (G1, G2, G3,...); This procedure outputs a weighted adjacency matrix W; where each weight indicates the uncertainty associated with the presence of each edge; Finally, we pass W to a radius function that aggregates each row of W and produces the uncertainty value for the node representing that row: Finally, we pass W to a radius function that aggregates each row of W and produces the uncertainty value for the node representing that row (Page 1). How do we define uncertainty in the model’s output? We utilize the student-teacher model [5, 6]; Specifically, we generate a teacher that takes the original graph G and produces a graph embedding Z; We then train a multi-layer perceptron (MLP) using the inputs and outputs of the teacher; The trained MLP is called the student; The student learns to predict α-quantiles and (1 − α)-quantiles for each dimension of ⃗zu (Recall that ⃗zu is a row in Z the output of the teacher function); Subsequently, we send the student’s prediction to a conformal learning algorithm [7] that refines the predicted quantiles; The distance between the quantiles averaged across all dimensions is our definition of uncertainty in the graph embedding function’s output. How do we incorporate data uncertainty and the uncertainty in the model’s output into the training procedure of a graph embedding function? We inject noise into the hidden representation of each node proportional to the uncertainty values (a.k.

Improvements for AI systems

Data Uncertainty Quantification: The system can quantify uncertainty in graph data by computing data dependent radii using eigen-decompositions and a consensus function that calculates uncertainty associated with edge presence based on reconstructed graph views. This allows the model to know when it is dealing with noisy or incomplete structural information.
Model Output Robustness: The system incorporates model output uncertainty using a student teacher model trained with quantile loss, refined by conformal learning to produce prediction intervals for each embedding dimension. This mechanism generates a radius value for each node representing the uncertainty in the graph embedding function's output, such that a given node u in a graph G maps exactly to z u in a given d-dimensional space is not guaranteed.
Robust Training via Noise Injection: The system incorporates these data and model radii into the training procedure by injecting noise into the hidden layer representations of each node proportional to its radius, sampled from a normal distribution with variance equal to that node's radius. This controlled instability compels the model to learn robust representations for uncertain nodes.
Curriculum Learning for Complexity: The system utilizes curriculum learning on graph views reconstructed with increasing numbers of components, starting from the most simplified version. This gradual introduction of complexity helps the model learn robust representations at each stage, as noted by the curriculum learning improves the accuracy of the model under adversarial attacks.

Abstract

Machine learning models for graphs in real-world applications are prone to two primary types of uncertainty: (1) those that arise from incomplete and noisy data and (2) those that arise from uncertainty of the model in its output. These sources of uncertainty are not mutually exclusive. Additionally, models are susceptible to targeted adversarial attacks, which exacerbate both of these uncertainties. In this work, we introduce Radius Enhanced Graph Embeddings (REGE), an approach that measures and incorporates uncertainty in data to produce graph embeddings with radius values that represent the uncertainty of the model's output. REGE employs curriculum learning to incorporate data uncertainty and conformal learning to address the uncertainty in the model's output. In our experiments, we show that REGE's graph embeddings perform better under adversarial attacks by an average of 1.5% (accuracy) against state-of-the-art methods.