# Fully Connected vs KNN Graph Topology in Doc2Graph: A Complete Guide

> Understand the difference between fully connected and KNN graph topology in Doc2Graph. Learn how to choose the right strategy for your document to graph conversions.

- Repository: [Andrea Gemelli/doc2graph](https://github.com/andreagemelli/doc2graph)
- Tags: deep-dive
- Published: 2026-02-24

---

**Doc2Graph uses two distinct wiring strategies—fully connected (O(N²) edges) and K-nearest neighbour (O(k·N) edges)—to balance expressive power against computational cost when converting documents into graph neural network inputs.**

The **andreagemelli/doc2graph** repository provides a framework for transforming document images into graph structures suitable for Graph Neural Networks (GNNs). A critical configuration choice when using this library is selecting the **graph topology**, which determines how nodes (textual elements) are connected by edges. The implementation supports switching between a dense fully connected topology and a sparse K-nearest-neighbour (KNN) approach via the `edge_type` parameter.

## What Is Graph Topology in Doc2Graph?

In Doc2Graph, **graph topology** refers to the algorithm used to create edges between nodes after OCR or layout analysis has extracted text boxes. Each node represents a document element (word, form field, or text block), and edges represent relationships the GNN will learn from.

The topology is controlled by the `GRAPHS.edge_type` configuration key (set in [`configs/base.yaml`](https://github.com/andreagemelli/doc2graph/blob/main/configs/base.yaml)) or overridden via the command-line flag `--edge-type`. Two values are supported:

- **`fully`** – Creates a complete graph where every node connects to every other node.
- **`knn`** – Creates a sparse graph where each node connects only to its *k* closest spatial neighbours.

## Fully Connected Graph Topology

### Implementation Details

The fully connected strategy is implemented in `GraphBuilder.fully_connected` within [`doc2graph/data/graph_builder.py`](https://github.com/andreagemelli/doc2graph/blob/main/doc2graph/data/graph_builder.py) (lines 100–114). This method iterates through all node pairs and creates an undirected edge between every distinct pair, resulting in a complete graph structure.

```python

# Simplified conceptual view of the fully_connected implementation

def fully_connected(self, num_nodes):
    edges = []
    for i in range(num_nodes):
        for j in range(i + 1, num_nodes):
            edges.append((i, j))
    return edges

```

### Computational Characteristics

A fully connected topology generates **O(N²)** edges, where *N* is the number of nodes. For documents with hundreds of text boxes, this creates dense adjacency matrices that consume significant GPU memory and increase training time. The approach treats every pair of words as potentially related, which can be advantageous for tasks requiring long-range dependencies (such as linking a distant key to its value) but computationally expensive for large documents.

## K-Nearest-Neighbour (KNN) Graph Topology

### Implementation Details

The KNN strategy is implemented in `GraphBuilder.knn_connection` within [`doc2graph/data/graph_builder.py`](https://github.com/andreagemelli/doc2graph/blob/main/doc2graph/data/graph_builder.py) (lines 115–188). Unlike the global connectivity of the fully connected approach, this method uses spatial locality to limit edges.

The algorithm:
1. Computes spatial distances between nodes using polar coordinates via `utils.polar`.
2. Expands a search window outward from each node until at least *k* neighbours are discovered.
3. Ranks candidates by distance and retains only the top *k* connections.

```python

# Example: Building a KNN graph with default k=10

from doc2graph.data.graph_builder import GraphBuilder

builder = GraphBuilder()
builder.edge_type = "knn"  # Activates knn_connection method

builder.k = 10  # Default value, configurable via GRAPHS.k in config

graphs, node_labels, edge_labels, features = builder.get_graph(
    src_path="/path/to/documents",
    src_data="FUNSD"
)

```

### Spatial Awareness and Distance Metrics

The KNN topology respects the **2-D layout** of the document. By using polar distance calculations, it prioritizes edges between physically proximate text elements—such as words in the same line or adjacent form fields. This creates **O(k·N)** edges, a linear relationship that remains tractable even for dense documents with many text regions. The default *k* value of 10 strikes a balance between local context and computational efficiency.

## Key Differences: Fully Connected vs KNN Graph Topology

| Feature | Fully Connected (`fully`) | KNN (`knn`) |
|---------|---------------------------|-------------|
| **Edge Count** | **O(N²)** – quadratic growth with node count | **O(k·N)** – linear growth (default k=10) |
| **Connection Logic** | Global: every node connects to all others | Local: nodes connect only to spatially nearest neighbours |
| **Spatial Awareness** | None; treats all pairs equally | High; uses polar distance and 2-D document layout |
| **Memory Usage** | High; dense adjacency matrices | Low; sparse graph structure |
| **Best For** | Tasks requiring long-range reasoning (e.g., cross-page key-value linking) | Layout-aware tasks (e.g., table detection, form understanding) |
| **Implementation** | `GraphBuilder.fully_connected` (lines 100–114) | `GraphBuilder.knn_connection` (lines 115–188) |

## Practical Code Examples

### Configuring Topology via Command Line

When running Doc2Graph training or inference, specify the topology using the `--edge-type` flag defined in [`doc2graph/main.py`](https://github.com/andreagemelli/doc2graph/blob/main/doc2graph/main.py):

```bash

# Train with fully connected topology

python -m doc2graph.main --edge-type fully --config configs/base.yaml

# Train with KNN topology (k=10 default)

python -m doc2graph.main --edge-type knn --config configs/base.yaml

```

### Programmatic Graph Construction

```python
from doc2graph.data.graph_builder import GraphBuilder

src_path = "/data/funsd"
src_data = "FUNSD"

# Fully connected example

builder_fc = GraphBuilder()
builder_fc.edge_type = "fully"
graphs_fc, _, _, _ = builder_fc.get_graph(src_path, src_data)
print(f"Fully connected edges: {graphs_fc[0].number_of_edges()}")

# KNN example (default k=10)

builder_knn = GraphBuilder()
builder_knn.edge_type = "knn"
graphs_knn, _, _, _ = builder_knn.get_graph(src_path, src_data)
print(f"KNN edges: {graphs_knn[0].number_of_edges()}")

```

## When to Use Each Topology

Choose **fully connected** when:
- Your task requires reasoning about relationships between distant document elements (e.g., linking a header on page one to a footer note on page three).
- Your documents contain few nodes (small forms or receipts) where O(N²) complexity remains manageable.
- You have abundant GPU memory and prefer to let the GNN learn which edges matter via attention mechanisms.

Choose **KNN** when:
- Processing layout-rich documents such as tables, multi-column reports, or complex forms where spatial proximity indicates semantic relationships.
- Scaling to documents with hundreds of text boxes, as the linear O(k·N) edge count prevents memory bottlenecks.
- You want to inject prior knowledge about document structure (nearby text is likely related) directly into the graph topology.

## Summary

- **Fully connected** and **KNN** are the two graph topologies available in Doc2Graph, controlled via the `edge_type` configuration parameter.
- **Fully connected** creates O(N²) edges by linking every node to every other node in `GraphBuilder.fully_connected`, suitable for small documents or long-range reasoning tasks.
- **KNN** creates O(k·N) edges by connecting each node to its k nearest spatial neighbours in `GraphBuilder.knn_connection`, respecting document layout and scaling to larger documents.
- Select the topology in [`configs/base.yaml`](https://github.com/andreagemelli/doc2graph/blob/main/configs/base.yaml) or via the `--edge-type` command-line flag when running [`doc2graph/main.py`](https://github.com/andreagemelli/doc2graph/blob/main/doc2graph/main.py).

## Frequently Asked Questions

### How do I switch between fully connected and KNN graph topology in Doc2Graph?

Set the `edge_type` parameter to either `"fully"` or `"knn"` in your configuration file ([`configs/base.yaml`](https://github.com/andreagemelli/doc2graph/blob/main/configs/base.yaml) under the `GRAPHS` section) or pass it as a command-line argument using `--edge-type` when executing [`doc2graph/main.py`](https://github.com/andreagemelli/doc2graph/blob/main/doc2graph/main.py). The `GraphBuilder` class reads this value to determine whether to invoke `fully_connected` or `knn_connection` during graph construction.

### What is the default value of k in KNN mode, and how does it affect performance?

The default value of **k is 10**, as defined in the configuration defaults. This means each node connects to its 10 nearest spatial neighbours, resulting in approximately 10N edges. Lower values (e.g., k=5) reduce memory usage and computation but may miss important relationships between moderately distant elements. Higher values increase connectivity but approach the computational cost of fully connected graphs; the default of 10 balances local context with efficiency for most document layouts.

### Does the fully connected topology ignore spatial information entirely?

Yes. The `fully_connected` method in [`doc2graph/data/graph_builder.py`](https://github.com/andreagemelli/doc2graph/blob/main/doc2graph/data/graph_builder.py) creates edges based solely on node existence, not spatial coordinates. Every pair of nodes receives an edge regardless of their physical distance in the document. While the nodes themselves retain positional features (coordinates), the topology treats a pair of words on opposite sides of a page identically to adjacent words. This makes the fully connected approach layout-agnostic but computationally expensive for dense documents.