topological sort and neural network pruning

by Darshan Surajmal

One studies topological sorting, an algorithmic method from graph theory, to prune neural networks efficiently. This is done by understanding dependencies between layers or neurons.

deliverables

1. Understanding Directed Acyclic Graphs (\(\mathbf{DAG}\)s) and Topological Sort

Introduce the concepts of graphs, directed graphs, and directed acyclic graphs (\(\mathbf{DAG}\)s). Explain what topological sort is and why it is only defined for DAGs.

Requirements

• Define graphs, directed graphs, and \(\mathbf{DAG}\)s with simple examples.
• Explain why cycles prevent topological sorting.
• Describe the purpose of topological sort.
• Bonus. Include a small \(\mathbf{DAG}\) and its topological order.

2. Topological Sort Algorithm and Complexity

Using Kahn’s algorithm, explain how the topological sort algorithm works and analyze its time complexity.

Requirements

• Present the algorithm steps clearly and concisely.
• Define the input (a \(\mathbf{DAG}\)) and output (a linear ordering).
• Provide a hand-drawn pseudocode or a flowchart.
• Analyze the Big-O time complexity and explain why it is efficient.

3. Applying Topological Sort to Neural Network Pruning

Describe how a neural network’s layers or neurons can be represented as a DAG and how topological sort helps prune redundant or unnecessary parts without breaking dependency order.

Requirements

• Discuss the neural network pruning problem.
• Transform the pruning problem to a \(\mathbf{DAG}\) problem. How can we do this, and what is the connection?
• What is topological order, and why is it important for the neural network?

4. Reflection

Reflect on the insights gained about the interplay between graph algorithms and neural networks.

Requirements

• Summarize key takeaways about topological sorting.
• Reflect on the challenges of applying graph theory in neural network optimization.

bonus deliverable

Model the following neural network as a Directed Acyclic Graph (\(\mathbf{DAG}\)) and perform pruning using topological sort. Use the rules provided below.

Pruning Rules

• Prune edges with weight \(< 0.5\)
• Remove orphaned nodes (nodes with no incoming edges except Input, no outgoing edges except Output)
• Process nodes in reverse topological order

Tasks

1. Generate a valid topological order (consider only edges, ignore weights)
2. Simulate pruning in reverse topological order:
   • For each node, prune incoming edges with weight \(< 0.4\)
   • Remove orphaned nodes immediately
   • Track graph changes at each step
3. Draw the final pruned network

Bonus. What happens when we prune without topological sort?¹

Resources

• Topological Sort Graph Algorithm. Tushar Roy.
• Topological Sorting. GeeksforGeeks.
• A beginner’s Guide to Neural Network Pruning. Vijaysinh Lendave.