Graphs as ML Data Structures

Adjacency formats, task types, permutation invariance, homophily, inductive vs transductive

A fraud detection system has 50 million users and 5 billion transactions. A user who received money from 5 confirmed fraud accounts last week is almost certainly a fraud risk. But your ML model takes a feature vector per user — age, account balance, transaction volume. None of those features capture "connected to known fraudsters." The signal is real, it is strong, and it is invisible unless you model the graph structure. This is why graph ML exists.

Graphs appear wherever relationships between entities carry information: molecular property prediction (atoms as nodes, bonds as edges), citation networks (papers as nodes, citations as edges), knowledge graphs (entities as nodes, relations as edges), social recommendations. In each case, the graph structure encodes relational signals that a per-node feature vector cannot represent. Graph ML extracts that signal.

Before any model runs, you need the right data structure. A 50M-node social graph stored as a dense adjacency matrix requires 50M × 50M entries at 1 bit each: 312 terabytes. Stored as a CSR (Compressed Sparse Row) sparse matrix with only the 5B actual edges, it requires about 40 gigabytes. This is not a detail — it is the difference between a system that is buildable and one that is not.

Beyond data structures, graph tasks split into three types. Node-level tasks (fraud detection, protein function prediction) require a prediction per node, using each node's final embedding directly. Edge-level tasks (link prediction, drug-target interaction) require a prediction per edge, typically from a decoder applied to the two endpoint embeddings. Graph-level tasks (molecular property prediction) require one prediction for the entire graph, using a readout function that aggregates all node embeddings into a fixed-size vector.

NOT this. "Graphs are just for network analysis." Graphs appear wherever entities have relationships that carry information: molecular property prediction where the graph is a molecule, recommendation systems where the graph connects users to items, knowledge graphs that power QA systems, traffic routing where roads are edges. Any problem with entities and relations between them is potentially a graph problem. The question is whether the relational structure contains signal that a per-entity feature vector would miss — and in most domains, it does.

Key points

• Dense adjacency matrix A ∈ {0,1}^{NxN}: stores all N² entries regardless of edge count. O(N²) memory. Efficient only for dense graphs (|E| ≈ N²). For a social graph with N=50M nodes: 50M×50M = 2.5×10^{15} entries, ~312 TB even at 1 bit per entry. GCN on full adjacency requires O(N²) memory even at inference. Never use for large sparse graphs.
• CSR (Compressed Sparse Row): stores only nonzero entries in three arrays — values (edge weights), col_indices (column of each entry), row_ptr (start of each row in col_indices). Memory O(|E| + |V|). For a 50M-node graph with 5B edges: ~40 GB. SpMM (sparse × dense matrix multiply) is the core GNN operation — PyTorch Geometric and DGL both build on this. Message passing on CSR is naturally parallel across edges, which maps directly to GPU execution.
• Node-level, edge-level, and graph-level tasks require fundamentally different output structures. Node-level (fraud detection, protein function): each node gets a prediction, using the node's final embedding directly. Edge-level (link prediction, knowledge graph completion): each edge gets a prediction, typically from a decoder applied to the two endpoint embeddings. Graph-level (molecular property, circuit quality): the entire graph gets a prediction, requiring a readout function that aggregates all node embeddings into a fixed-size vector.
• Standard NNs cannot be applied to graphs for two reasons: variable input size (graphs differ in |V| and |E|), and no canonical node ordering — the same node appears at index 3 in one ordering and index 87 in another. Permutation invariance requires f(PAP^T, Px) = f(A, x) for any permutation matrix P. An MLP applied to a flattened adjacency matrix is not permutation invariant — different orderings of the same graph produce different outputs.
• Graph signal processing gives structural intuition: node features are signals on the graph. The graph Laplacian L = D - A captures discrete gradient structure. Multiplying by L computes the difference between each node's feature and its neighbors' mean — a high-pass filter that amplifies differences. GCN aggregation with self-loops is a low-pass filter that smooths features across edges. Stacking too many GCN layers over-smooths features to the point where all nodes become indistinguishable; residual/skip connections (carrying each layer's input forward) or simply keeping depth shallow (2–4 layers) are the standard fixes.
• Homophily vs heterophily determines whether mean aggregation helps or hurts. In homophilic graphs (social networks — connected nodes have similar properties), standard GNNs that average neighbor features work well because neighbors have informative features. In heterophilic graphs (fraud ring members connect to victims, bipartite recommendation graphs), mean aggregation destroys the discriminative signal because the fraudster's neighbors are predominantly legitimate. H2GCN addresses this by keeping the ego node's embedding separate from aggregated neighbor features, and by aggregating 1-hop and 2-hop neighborhoods separately and concatenating them rather than mixing all distances together — heterophilic signal often shows up more strongly at 2 hops than at 1.
• Inductive vs transductive is an architectural commitment with production consequences. Transductive GNNs (spectral methods, vanilla GCN) train and test on the same fixed graph — they cannot generate embeddings for unseen nodes without retraining. In production, new users and items arrive continuously. GraphSAGE, GAT, and spatial methods learn aggregation functions that apply to any neighborhood, making them inductive by design. Anything requiring full graph retraining to embed new nodes is not deployable.
• Heterogeneous graphs are the production default. Multiple node types (user, item, category) and edge types (click, purchase, co-viewed) are the norm in e-commerce and knowledge graphs. Homogeneous GNNs that ignore type information discard the relational semantics that distinguish a click from a purchase — which are often the most commercially important signals. Modeling heterogeneity is not an advanced feature; ignoring it is a lossy baseline.

Recap

• Graph ML exists for relational signal: "connected to known fraudsters" is invisible to a per-node feature vector.
• Dense adjacency is O(N²): 50M nodes → ~312 TB. CSR stores only edges → ~40 GB. Format decides buildability.
• Three task types: node-level (per-node embedding), edge-level (decoder on 2 endpoints), graph-level (readout aggregates all nodes).
• Permutation invariance is the defining constraint: N! orderings → aggregate with sum/mean/max; MLP on flattened $A$ is not invariant.
• Homophily → mean aggregation helps; heterophily → it destroys signal (fraud rings connect to victims).
• Inductive vs transductive is a deployment commitment: vanilla GCN can't embed unseen nodes; GraphSAGE/GAT can.
• Heterogeneous graphs are the production default — ignoring node/edge types is a lossy baseline.

Check your understanding