AI Glossary / Mathematics and optimization / Intermediate
Edge weight
Definition
An edge weight is a numerical value associated with a connection between two nodes in a graph. It can represent a cost, distance, capacity, similarity or another quantity defined by the model. The meaning determines how the weight should be used. In the supplied source's federated-learning network convention, weights are nonnegative and a zero weight denotes an absent connection.
What it means
A graph says which entities are connected; weights add information about those connections. A larger value might mean a longer journey in a transport graph, but a stronger relationship in a similarity graph. Those interpretations lead to different computations. The term alone does not imply that weights are probabilities or that they sum to one. It also does not make an edge weight interchangeable with a neural-network parameter, even though both are numerical quantities called weights.
How it works
Begin by defining nodes, edges and the quantity attached to each edge. Store weights in an edge list, adjacency structure or matrix, while preserving direction if the graph is directed. Then use an algorithm that interprets those values appropriately. A weighted shortest-path calculation adds costs along a path and minimizes their sum. A capacity-constrained flow calculation treats weights as limits rather than additive journey costs. In graph-based learning, nonnegative affinity weights can control how strongly connected nodes influence an objective. Missing connections and valid zero-valued connections need distinct representations whenever the application allows both.
Three practical examples
- A delivery graph can attach travel time to each road segment so route selection minimizes total modeled time.
- A document graph can attach similarity scores to connections, helping a clustering method express which documents belong near one another.
- A federated-learning network can assign nonnegative strengths to relationships between participants, according to the particular communication or coupling model being used.
Think of it this way
Think of writing numbers beside lines on a map. A label of 8 could mean eight minutes, eight lanes or a relationship score of eight. The drawing alone cannot tell you which calculation is sensible. The analogy emphasizes the need for a legend, but a mathematical graph can represent abstract relationships without any geographical interpretation, and some algorithms transform weights before using them.
Worked example
Consider an undirected graph with travel-time weights AB = 4 minutes, BC = 3 minutes and AC = 10 minutes. The direct A-to-C route has one edge and costs 10 minutes. The route through B has two edges and costs 4 + 3 = 7 minutes, so the weighted shortest route differs from the route with the fewest edges. Now consider a separate similarity graph on the same nodes, with AB = 4, BC = 1 and AC absent. Suppose a graph-regularization term is R = Σ wij(zi − zj)², with each undirected edge counted once, and node values are zA = 0, zB = 2 and zC = 3. Then R = 4(0 − 2)² + 1(2 − 3)² = 17. If zB changes to 1 while the others stay fixed, R becomes 4(0 − 1)² + 1(1 − 3)² = 8. The stronger AB weight makes disagreement across that edge more costly. This second calculation is a separate model, not a reinterpretation of the travel-time numbers as evidence of similarity. Counting each undirected edge twice would double R, so the convention must be stated.
Illustrative case study
In a fictional project, Alder Analytics builds a graph of service locations. One dataset labels edges with driving time; another labels them with demand-pattern similarity. Analysts keep these attributes separate and choose the relevant one for each calculation. A review catches an attempted clustering run using raw driving time as if larger values meant stronger affinity. The team corrects the representation before interpreting the clusters. The case illustrates a modeling error and its correction, not a claim of improved operational results.
Common misconceptions and mistakes
A high weight is not always good, and a low weight is not always weak. The interpretation depends on the task. Zero does not universally mean no edge: a valid zero-cost connection can exist in a cost graph, although the supplied FL convention uses zero for absence. Negative weights are possible in some graph models, but algorithms impose conditions; standard Dijkstra reasoning requires nonnegative costs. Finally, storing a weight does not ensure that software uses it. An unweighted algorithm may ignore the attribute and count edges instead.
Business use
Document units, direction, permitted values and the meaning of missing data. Confirm that the selected algorithm reads the intended weight attribute. Test a small graph with a result that can be computed by hand, including a case where the weighted answer differs from the unweighted answer. For similarity graphs, explain how similarities were estimated and whether they were thresholded or normalized. For time-dependent costs, preserve the observation period. In learned graph models, inspect sensitivity to weight changes rather than treating uncertain relationships as exact facts.
People also ask
Must edge weights sum to one?
No. Normalization is required only by particular models, such as a specified transition-probability representation.
Can the same pair of nodes have different weights in opposite directions?
Yes, in a directed graph, if the application defines distinct directional relationships.
Does zero weight always remove a connection?
No. That is a representation convention in some models; others distinguish a zero-cost edge from no edge.
Check your understanding
In the travel-time example, why is A - B - C preferable despite using more edges?
Answer: Its total modeled travel time is 7 minutes, compared with 10 minutes for the direct edge. Weighted shortest paths minimize the sum of costs, not necessarily the number of connections.
Related terms
- Weighted graph
- Shortest Paths
- Similarity graph
- adjacency matrix
- shortest path
- graph Laplacian
- network flow
Learn next
change AC's travel time to 6 minutes and recompute the best route. Then keep the similarity graph separate and vary AB's affinity in the regularization calculation. Explain why increasing the weight has different practical meanings in the two examples.
More in Mathematics and optimization
- Absolute error loss - Absolute error loss measures a numerical prediction's error as the absolute difference between its predicted and reference values: L(y,y-hat)=|y-y-hat|.
- Active-set method - An active-set method is an optimization approach that works with a changing subset of constraints believed to be tight at the solution.
- Adjoint state method - The adjoint state method computes how a chosen objective changes when the parameters of a mathematical model change.
- Σ-algebra
- Algebraic connectivity - Algebraic connectivity is the second-smallest eigenvalue of a graph's Laplacian matrix.
- Algorithm IMED - Algorithm IMED, short for Indexed Minimum Empirical Divergence, is a method for choosing actions in a stochastic multi-armed bandit problem.
Sources
Sources: Jung and colleagues, The Aalto Dictionary of Machine Learning, edge weight and weighted graph entries, https://aaltodictionaryofml.github.io/ADictML_Main.pdf ; NetworkX, Shortest Paths documentation, https://networkx.org/documentation/stable/reference/algorithms/shortest_paths.html . The route, quadratic graph penalty and fictional review case are original examples. The source-specific zero-weight convention is distinguished from general graph usage.
Previous: Edge-spread function Next: Edgelist