In addition to the graph structure itself consisting of nodes and edges, information is typically associated with each node. For example, in a social network, each individual might be characterized by a fixed-length vector representing their interests. Sometimes, the edges also have information attached. For example, for a road network, each edges might be characterized by its length, number of lanes, frequency of accidents, and speed limit. The information at a node is stored in a node embedding, and the information at an edge stored in an edge embedding.
Formally, a graph consists of a set of nodes connected by a set of edges. The graph can be encoded by three matrices , representing the graph structure, node embeddings, and edge embeddings.
The graph structure is represented by the adjacency matrix . This is an matrix where each entry is set to one if there is an edge between nodes and and zero otherwise. For undirected graphs, this matrix is always symmetric. For large sparse graphs, it can be stored as a list of connections to save memory.
The -th node has an associated node embedding of length . These embeddings are concatenated and stored in the node data matrix . Similarly, the -th edge has an associated edge embedding of length . These embeddings are collected into the matrix .