Graph Properties: Degree, Connectivity, and Paths
You'll learn how to measure fundamental structural properties of graphs that determine how information flows through networks.
Understanding Core Graph Properties
Graphs aren't just collections of nodes and edges—their structure matters tremendously for machine learning tasks. Three fundamental properties help characterize this structure:
Node Degree
The degree of a node is simply how many edges connect to it. Think of it like counting someone's friends in a social network. In directed graphs, you distinguish between in-degree (incoming edges) and out-degree (outgoing edges). High-degree nodes are often "hubs" that play outsized roles in information diffusion.
Graph Connectivity
Connectivity describes whether you can reach any node from any other node by following edges. A graph is connected if there's at least one path between every pair of nodes. In social networks, disconnected components might represent isolated communities. This property determines whether information can flow globally or remains trapped in clusters.
Paths and Distance
A path is a sequence of edges connecting two nodes. The shortest path between nodes is the path with the fewest edges (or minimum total weight in weighted graphs). The diameter of a graph is the longest shortest path between any pair of nodes—essentially measuring how "wide" the graph is. Small-world networks (like social graphs) have surprisingly short diameters despite having millions of nodes.
Why This Matters for GNNs
Graph Neural Networks use these structural properties to determine how information propagates. Node degree influences aggregation (high-degree nodes pool information from many neighbors), connectivity determines which nodes can influence each other, and path lengths affect how many GNN layers you need to capture long-range dependencies.
Key Takeaway: Node degree, connectivity, and path structure are fundamental graph properties that govern information flow and directly influence how Graph Neural Networks process and learn from graph-structured data.