Algorithms on Graphs

Scope of this lecture

• Importance of graph algorithms
• Types of graph algorithms
• Applications and Implementation

Why graph algorithms?

• Graphs are used to model relationships between objects.
• Graphs has a powerful representation of data.

If we want to use this data, we need to process it.

• Graph algorithms : compute properties from graphs, explore graphs
• Graph machine learning : build predictive models from graphs

Different types of algorithms

• Traversal Algorithms
  • Breadth-First Search (BFS) and Depth-First Search (DFS)
  • Shortest Path Algorithms (Dijsktra's)
  • Maximum Flow Algorithms (Ford-Fulkerson)
  • Minimum Spanning Tree Algorithms
• Clustering Algorithms
  • Community Detection Algorithms
  • Spectral Clustering Algorithms
• Graph Comparison Algorithms
  • Graph Matching Algorithms
  • Graph Isomorphism Algorithms

Graph Representation

• Adjacency Matrix
• Adjacency List
• Edge List

Algorithms can operate on any representation. The choice of representation depends on the algorithm and the problem.

Breadth-First Search (BFS)

Starts at the root node and explores all the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.

BFS Algorithm

1. Initialize a queue and enqueue the starting node.
2. Mark the starting node as visited.
3. While the queue is not empty:
   1. Dequeue a node from the queue.
   2. Process the dequeued node.
   3. Enqueue all adjacent unvisited nodes and mark them as visited.
4. Repeat until all nodes are processed.

Depth-First Search (DFS)

Starts at the root node and explores as far as possible along each branch before backtracking. This approach uses a stack data structure, either implicitly through recursion or explicitly.

DFS Algorithm

1. Initialize a stack and push the starting node.
2. Mark the starting node as visited.
3. While the stack is not empty:
   1. Pop a node from the stack.
   2. Push all adjacent unvisited nodes onto the stack and mark them as visited.
4. Repeat until all nodes are processed.

Example

Starting from node A :

• BFS : A, B, C, D, E, F.
• DFS traversal order would be: A, B, D, F, C, E.

Both algorithms constitues the basis of many other graph algorithms.

Shortest Path

Shortest path :minimum path between two nodes in a graph.

Minimum path can be defined in different ways:

• Unweighted Graphs: The minimum number of edges between two nodes.
• Weighted Graphs: The minimum sum of edge weights between two nodes.

Dijsktra's Algorithm

Shortest path from a source node to all other nodes in a graph.

function Dijkstra(Graph, source):
       for each vertex v in Graph.Vertices:
           dist[v] ← INFINITY
           prev[v] ← UNDEFINED
           add v to Q
       dist[source] ← 0
       while Q is not empty:
          u ← vertex in Q with minimum dist[u]
          remove u from Q
          for each neighbor v of u still in Q:
              alt ← dist[u] + Graph.Edges(u, v)
              if alt < dist[v]:
                  dist[v] ← alt
                  prev[v] ← u
      return dist[], prev[]

Random Walks

A random walk on a graph is a stochastic process that describes a path consisting of a succession of random steps on the graph.

Algorithm

1. Start at an initial node.
2. At each step, move to a randomly chosen adjacent node.
3. Repeat for a specified number of steps or until a stopping condition is met.

Flow Algorithms

Flow algorithms are used to find the maximum flow in a network. The maximum flow is the maximum amount of flow that can be sent from the source to the sink.

Ford-Fulkerson Algorithm

• Ford-Fulkerson algorithm is used to find the maximum flow in a network.
• It uses the concept of residual capacity to find the augmenting paths.

1. Initialize flow to 0.
2. While there is a path from source to sink:
    a. Find the maximum flow through the path.
    b. Update the capacities of the edges and reverse edges along the path.
3. Return the maximum flow.

Powers of Adjacency Matrix to Compute Paths

• The adjacency matrix corresponds to paths of length 1.
• Paths of length 2 : Combination of two paths of length 1 connecting together.
  : paths of length 2
• And so on : : Matrix of paths of lengh .

Spectral Clustering

Graph Cut : divide the nodes into two groups while minimizing the connections between them:

Minimizing the cut is challenging, but Spectral Clustering uses a relaxation based on eigenvalues and eigenvectors.

Relaxation and Eigenvectors

To minimize the cut, we relax the problem by decomposing the Laplacian matrix ( L ) to obtain eigenvectors and eigenvalues:

The eigenvectors associated with the smallest eigenvalues provide an approximation to minimize the cut.

The First Non-trivial Eigenvector

The first non-trivial eigenvector (associated with the smallest non-zero eigenvalue) is crucial for cut minimization.

• It naturally separates nodes in the graph according to their connectivity.
• We can classify nodes based on the sign of the elements in .

Partitioning with the First Eigenvector

Using , we define a simple partition:

This partition tends to minimize the cut by exploiting the spectral structure of .

Intuitive Explanation

• The first non-trivial eigenvector acts as a filter, separating weakly connected nodes.
• The smaller , the smaller the cut between clusters, indicating a natural separation.

Extension to Clustering into Clusters

1. Compute the first eigenvectors of the Laplacian matrix, excluding the zero eigenvector.
2. Construct a matrix from these eigenvectors where each row represents a node's coordinates.
3. Apply k-means clustering on the rows of , resulting in clusters.

Why Minimize the Cut?

Minimizing the cut helps:

• Identify well-separated groups within the graph.
• Reduce the impact of weak connections.

Spectral Clustering optimizes clustering through a spectral analysis that captures the underlying structure.

Application to Karate Club

Conclusion on spectral clustering

• The first non-trivial eigenvector is essential for minimizing the cut.
• Spectral Clustering extends naturally to clustering using multiple eigenvectors.
• This method is ideal for graphs where clusters are defined by strong connections and clear separations.
• More on that : A Tutorial on Spectral Clustering

Page Rank

A famous graph algorithm

PageRank is an algorithm used by Google Search to rank web pages in their search engine results. It measures the importance of website pages.

Formula

• : PageRank of page
• : factor usually set to 0.85, : Total number of pages
• : pages linking to
• : Number of outbound links on page

Matrix/Graph Representation

We want to solve where is the PageRank matrix.

Graph Isomorphism

How to compute if two graph are isomorphic ?

• Graph Isomorphism : Two graphs are isomorphic if there is a bijection between their nodes that preserves the edges.

First approach : Find the bijection

• Naive approach : Try all possible bijections and check if the edges are preserved.

• Tree Search : Use a tree search algorithm to find the bijection.

First approach : Find the bijection

• in the worst case.

• Possibility to prune the search tree with heuristics.

• : Use a heuristic to guide the search.

Accelerate the isomorphism test

To accelerate, relax the match.

• Beam-search : Keep the best candidates at each level.

• Biparite matching : Find the best matching between the nodes.

• Weisfeiler-Lehman Algorithm : Label the nodes with their neighborhood structure.

Bipartite Graph Matching

Define a graph with and the edges between and .

• Bipartite Matching : Find the best matching between the nodes of and
• Hungarian Algorithm : Find the best matching in .

• How to match two nodes :
  • Compare the nodes' neighbors.
  • Compare the nodes' labels

Detect if two graphs are not isomorphic. But may say that two graphs are isomorphic when they are not.

Weisfeiler-Lehman Algorithm

see David Bieber's post

• Purpose: An efficient heuristic for graph isomorphism testing.
• Concept:
  • Iteratively refines node labels based on neighborhood structures.
  • Captures the graph's topology through label updates.

The WL Algorithm: Initialization

• Initial Labels:
  • Assign initial labels to all nodes (often all nodes start with the same label).
• Goal:
  • Differentiate nodes based on their structural roles.

The WL Algorithm: Iterative Refinement

1. Collect Neighbor Labels:
   • For each node, gather labels of its neighbors.
2. Relabeling:
   • Combine the node's and neighbor's label into a multiset.
   • Hash the multiset to produce a new label.
3. Repeat:
   • Continue iterations until labels stabilize.

The WL Algorithm: Iterative Refinement

1. Collect Neighbor Labels:
   • For each node, gather labels of its neighbors.
2. Relabeling:
   • Combine the node's and neighbor's label into a multiset.
   • Hash the multiset to produce a new label.
3. Repeat until label partitions stabilize.

Example of WL Refinement

• Iteration 1:
  • Nodes with different degrees get different labels.
    

Example of WL Refinement

• Iteration 2:

  • Nodes are further distinguished based on the labels of their neighbors.

Example of WL Refinement

• Outcome:
  • If two graphs have different label distributions, they are not isomorphic.

Limitations of the WL Test

• False Positives:
  • Some non-isomorphic graphs may produce identical label distributions.

Extensions: The k-WL Test

• Higher Dimensional WL Tests:
  • k-WL Test considers k-tuples of nodes.
  • Increases the algorithm's distinguishing power.
• Trade-off:
  • Higher computational complexity.

Applications of the WL Test

• Graph Isomorphism:
  • Efficiently distinguishes many non-isomorphic graphs.
• Machine Learning:
  • Graph kernels for classification tasks.
  • Graph Neural Networks theory and analysis.

Graph edit distance

• Dissimilarity measure
• Quantify a distortion

Graph edit distance

Minimal amount of distortion required to transform one graph into another.

• Edit path : Sequence of edit operations :

• Elementary edit cost :

Formal definition

• Edit path cost

• Edit distance

• Optimal edit path:

How to compute the Graph Edit Distance

Tree Search : Explore the space of possible edit paths.

Tree search methods

A∗

• Dijkstra-based algorithm
• Need an heuristic
  Always find a solution ...
  But may take a loooooong time
  Exponential number of edit paths

Depth first search based algorithm [Abu-Aisheh et al., 2015]

• Based on heuristic
• Limitation on the number of open paths
  Any time algorithm: can return an approximation before termination
  Parallelizable

Correspondence betweek edit paths and mappings

• An edit path corresponds to a mapping

Computing Graph Edit Distance Finding an Optimal Assignment

Cost

Mapping

Note: A mapping can be encoded by a permutation matrix

Cost Matrix

Node Operations Cost

Node cost induced by

Vectorized version

Edges Operations Cost

Edge cost matrix

• deletion operation; - insertion operation
• Edge's mapping is induced by nodes mapping

Edge's cost

Vectorized version

QAP Formulation of GED

An Intractable Problem

1. Any mapping corresponds to an edit path

2. Any edit path is optimal or sub-optimal

3. Edit path cost is optimal or sub-optimal

4. Approximate mapping Overestimation of GED

A First Approach

Linear Approximation

• [Riesen, 2009; Gauzere et al., 2014; Carletti et al., 2015]
• Linear approximation of QAP formulation
• Hungarian algorithm:

No structural information

Augmented Cost Matrix

Adding Some Structural Information

• : cost of mapping neighborhood of to neighborhood of
  • Direct neighborhood
  • Random walks
  • Subgraphs
• Complexity Accuracy

A First QAP Approach

Gradient Descent Approach

• Let's find a local minimum of
• Relax problem to continuous domain

Some solvers exist
No consideration of discrete nature of solution

Another Strategy

Integer-Projected Fixed Point (IPFP) [Leordeanu et al., 2009]

Frank-Wolfe-like algorithm

Iterate until convergence:

1. Discrete resolution of linear gradient of QAP
2. Line search between and the solution found in step 1

Operating IPFP

At Convergence

• Optimal continuous solution is stable
• Need a projection step to embed to
  Uncontrolled loss
  No guarantees that

Importance of Initialization

• Local minimum
  Initialization is important [Carletti et al., 2015]

GNCCP Approach [Liu et al., 2014]

From Convex to Concave Objective Function

GNCCP Algorithm

• Initialize
• For from to (e.g., decrement by each iteration)
  • Solve for minimizing
  • Update

Iterates over a modified IPFP objective function

From to

From to

GNCCP vs. IPFP

Pros

No need for initialization
Converges towards a mapping matrix (Birkhoff Polytope)

Cons

Complexity: Iterates over IPFP

Conclusion on Graph Edit Distance

Pros

• A nice and well-defined framework
• The distance can be used for projection, k-NN, etc.
• Good approximation
• Flexible: similarity depends on edit costs

Cons

• Still too long to compute for large graphs (≈1000 nodes)
• Need to tune edit costs
• We only have a distance...
• ... And this distance is non-Euclidean