graph representation

Lecture 21: Graph Representations and Traversals

A directed graph G is an ordered pair ( V , E ) consisting of a set of vertices or nodes V = { v 1 ,...,v n } and a set of edges or arcs E ⊆ V 2 . Generally we denote the number of vertices by | V | or n and the number of edges by | E | or m .

Directed graphs are commonly represented as an adjacency list , which comprises an array or list of vertices, where each vertex v i stores a list of all the vertices v j for which there is an edge ( v i , v j ) ∈ E .

Another common representation is an adjacency matrix , which is a two-dimensional array, where A i j is non-zero when there is an edge ( v i , v j ) ∈ E . In practice, many graphs are sparse in the sense that most of the possible edges between pairs of vertices do not exist, i.e. m n 2 . In such cases the adjacency list is generally preferable to the adjacency matrix representation.

Edges can sometimes additionally have an integer weight , which can be used to represent distances or costs.

Here is a simple directed graph with four vertices V = {1, 2, 3, 4} and four edges E = {(1, 2), (2, 3), (3, 1), (3, 4)}.

[1] | | / | v / v [2] [4]

Consider the following abstract data type for a directed graph with weighted edges. Note that while this specification does not explicitly require any particular implementation, the required running times of some of these functions constrain the implementation in various ways. For instance, a naive adjacency matrix implementation would take Θ( n 2 ) time to consider every array entry in producing a list of all the edges. However the edges function is required to do this in O( n + m ) time.

Note that the create function creates and returns an empty graph. The add_vertex function takes a graph as argument, adds a new singleton vertex to that graph (a vertex with no edges starting or ending at that vertex), and returns the new vertex. The function add_edge takes two vertices and a weight and joins the vertices together by an edge. These are all O(1) time operations.

The abstraction also provides operations for getting the list of vertices and edges of a graph, as well as the list of outgoing edges from a given vertex. There is also a function incoming_ref which returns a list of reversed edges, by taking all the incoming edges for a given vertex and turning them into edges that go in the opposite direction. This function is useful for exploring the back-edges in a graph (i.e., exploring the reversed graph where all the edge directions are swapped).

The Graph module in graph.ml implements this signature using adjacency lists of vertices, where both the outgoing edge list and the incoming edge for each vertex are explicitly represented. That is, each edge is stored twice, once at its source vertex and once at its destination vertex. This makes it easy to traverse the edges of the graph in reverse, which is useful for things like computing connected components (described below).

In that implementation, a graph is represented as a pair consisting of the number of vertices and a list of vertices. A vertex is represented as a triple of a unique integer id, an outgoing list, and an incoming list. The outgoing list is a list of pairs of destination vertex and weight. The incoming vertex list is a list of pairs of source vertex and weight. Note that as each edge is stored twice, in the incoming list of its destination and the outgoing list of its source, the weight must be consistent in the two lists.

In that implementation, an edge is a triple of a source vertex, destination vertex and weight, and is constructed on the fly as needed from the vertex out lists rather than being explicitly stored in the data structure.

Graph Traversals

One of the most basic graph operations is to traverse a graph, finding the nodes accessible by following edges from some starting node. You have already seen this operation in CS2110. We mark the vertices as visited when we have visited them to keep track of the parts of the graph that we have already explored. We start with a single vertex and mark it as visited. We then consider each outgoing edge. If an edge connects to an unvisited node, we put that node in a set of nodes to explore. Then we repeatedly remove a node from the set, mark it as visited, and repeat the process with that node. If we ever take a node out of the set and it is already marked as visited, then we ignore it.

The order in which we explore the vertices depends on how we maintain the set of vertices to explore. If we use a queue, so the unvisited vertices are explored in a first-in-first-out (FIFO) fashion, then the above traversal process it is known as breadth-first search (BFS). If we use a stack, so the unvisited vertices are explored in a last-in-first-out (LIFO) fashion, this is known as depth-first search (DFS).

Of course, such a traversal will only visit nodes reachable from the start node by a directed path.

Here is an implementation of traversal in a directed graph using the above abstraction. This implementation makes use of a set of vertices of type VSet to keep track of the visited vertices. It performs a BFS or DFS depending on whether the Queue or Stack package is opened. It also can traverse either the edges of the graph or of the ''reverse'' graph (in which all the edges have been reversed), based on the parameter dir .

Connected Components

In an undirected graph, a connected component is the set of nodes that are reachable by traversal from some node. The connected components of an undirected graph have the property that all nodes in the component are reachable from all other nodes in the component. In a directed graph, however, reachable usually means by a path in which all edges go in the positive direction, i.e. from source to destination. In directed graphs, a vertex v may be reachable from u but not vice-versa. For instance, for the graph above, the set of nodes reachable from any of the nodes 1, 2, or 3 is the set {1, 2, 3, 4}, whereas the set of nodes reachable from node 4 is just the singleton {4}.

The strongly connected components in a directed graph are defined in terms of the set of nodes that are mutually accessible from one another. In other words, the strongly connected component of a node u is the set of all nodes v such that v is reachable from u by a directed path and u is reachable from v by a directed path. Equivalently, u and v lie on a directed cycle. One can show that this is an equivalence relation on nodes, and the strongly connected components are the equivalence classes. For instance, the graph above has two strongly connected components, namely {1, 2, 3} and {4}.

It is possible to show that the strongly connected component from a node v i can be found by searching for nodes that are accessible from v i both in G and in G rev , where G rev has the same set of vertices as G , and has the reverse of each edge in G . Thus the following simple algorithm finds the strongly connected components.

Topological Ordering

Learn Python practically and Get Certified .

Popular Tutorials

Popular examples, reference materials, learn python interactively, dsa introduction.

• What is an algorithm?
• Data Structure and Types
• Why learn DSA?
• Asymptotic Notations
• Master Theorem
• Divide and Conquer Algorithm

Data Structures (I)

• Types of Queue
• Circular Queue
• Priority Queue

Data Structures (II)

• Linked List
• Linked List Operations
• Types of Linked List
• Heap Data Structure
• Fibonacci Heap
• Decrease Key and Delete Node Operations on a Fibonacci Heap

Tree based DSA (I)

• Tree Data Structure
• Tree Traversal
• Binary Tree
• Full Binary Tree
• Perfect Binary Tree
• Complete Binary Tree
• Balanced Binary Tree
• Binary Search Tree

Tree based DSA (II)

• Insertion in a B-tree
• Deletion from a B-tree
• Insertion on a B+ Tree
• Deletion from a B+ Tree
• Red-Black Tree
• Red-Black Tree Insertion
• Red-Black Tree Deletion

Graph based DSA

• Graph Data Structure
• Spanning Tree
• Strongly Connected Components

Adjacency Matrix

Adjacency List

• DFS Algorithm
• Breadth-first Search
• Bellman Ford's Algorithm

Sorting and Searching Algorithms

• Bubble Sort
• Selection Sort
• Insertion Sort
• Counting Sort
• Bucket Sort
• Linear Search
• Binary Search

Greedy Algorithms

• Greedy Algorithm
• Ford-Fulkerson Algorithm
• Dijkstra's Algorithm
• Kruskal's Algorithm

Prim's Algorithm

• Huffman Coding
• Dynamic Programming
• Floyd-Warshall Algorithm
• Longest Common Sequence

Other Algorithms

• Backtracking Algorithm
• Rabin-Karp Algorithm

DSA Tutorials

Depth First Search (DFS)

Graph Data Stucture

A graph data structure is a collection of nodes that have data and are connected to other nodes.

Let's try to understand this through an example. On facebook, everything is a node. That includes User, Photo, Album, Event, Group, Page, Comment, Story, Video, Link, Note...anything that has data is a node.

Every relationship is an edge from one node to another. Whether you post a photo, join a group, like a page, etc., a new edge is created for that relationship.

All of facebook is then a collection of these nodes and edges. This is because facebook uses a graph data structure to store its data.

More precisely, a graph is a data structure (V, E) that consists of

• A collection of vertices V
• A collection of edges E, represented as ordered pairs of vertices (u,v)

In the graph,

• Graph Terminology
• Adjacency : A vertex is said to be adjacent to another vertex if there is an edge connecting them. Vertices 2 and 3 are not adjacent because there is no edge between them.
• Path : A sequence of edges that allows you to go from vertex A to vertex B is called a path. 0-1, 1-2 and 0-2 are paths from vertex 0 to vertex 2.
• Directed Graph : A graph in which an edge (u,v) doesn't necessarily mean that there is an edge (v, u) as well. The edges in such a graph are represented by arrows to show the direction of the edge.
• Graph Representation

Graphs are commonly represented in two ways:

1. Adjacency Matrix

An adjacency matrix is a 2D array of V x V vertices. Each row and column represent a vertex.

If the value of any element a[i][j] is 1, it represents that there is an edge connecting vertex i and vertex j.

The adjacency matrix for the graph we created above is

Since it is an undirected graph, for edge (0,2), we also need to mark edge (2,0); making the adjacency matrix symmetric about the diagonal.

Edge lookup(checking if an edge exists between vertex A and vertex B) is extremely fast in adjacency matrix representation but we have to reserve space for every possible link between all vertices(V x V), so it requires more space.

2. Adjacency List

An adjacency list represents a graph as an array of linked lists.

The index of the array represents a vertex and each element in its linked list represents the other vertices that form an edge with the vertex.

The adjacency list for the graph we made in the first example is as follows:

An adjacency list is efficient in terms of storage because we only need to store the values for the edges. For a graph with millions of vertices, this can mean a lot of saved space.

• Graph Operations

The most common graph operations are:

• Check if the element is present in the graph
• Graph Traversal
• Add elements(vertex, edges) to graph
• Finding the path from one vertex to another

Table of Contents

• Introduction

Sorry about that.

Our premium learning platform, created with over a decade of experience and thousands of feedbacks .

Learn and improve your coding skills like never before.

• Interactive Courses
• Certificates
• 2000+ Challenges

Related Tutorials

DS & Algorithms

Data Structures and Algorithms

Chapter 10 graphs.

Show Source |    | About    «   9. 12. Hashing Chapter Summary Exercises   ::   Contents   ::   10. 2. Graph Implementations   »

10. 1. Chapter Introduction: Graphs ¶

10. 1.1. graph terminology and implementation ¶.

Graphs provide the ultimate in data structure flexibility. A graph consists of a set of nodes, and a set of edges where an edge connects two nodes. Trees and lists can be viewed as special cases of graphs.

Graphs are used to model both real-world systems and abstract problems, and are the data structure of choice in many applications. Here is a small sampling of the types of problems that graphs are routinely used for.

Modeling connectivity in computer and communications networks.

Representing an abstract map as a set of locations with distances between locations. This can be used to compute shortest routes between locations such as in a GPS routefinder.

Modeling flow capacities in transportation networks to find which links create the bottlenecks.

Finding a path from a starting condition to a goal condition. This is a common way to model problems in artificial intelligence applications and computerized game players.

Modeling computer algorithms, to show transitions from one program state to another.

Finding an acceptable order for finishing subtasks in a complex activity, such as constructing large buildings.

Modeling relationships such as family trees, business or military organizations, and scientific taxonomies.

The rest of this module covers some basic graph terminology. The following modules will describe fundamental representations for graphs, provide a reference implementation, and cover core graph algorithms including traversal, topological sort, shortest paths algorithms, and algorithms to find the minimal-cost spanning tree. Besides being useful and interesting in their own right, these algorithms illustrate the use of many other data structures presented throughout the course.

A graph \(\mathbf{G} = (\mathbf{V}, \mathbf{E})\) consists of a set of vertices \(\mathbf{V}\) and a set of edges \(\mathbf{E}\) , such that each edge in \(\mathbf{E}\) is a connection between a pair of vertices in \(\mathbf{V}\) . 1 The number of vertices is written \(|\mathbf{V}|\) , and the number of edges is written \(|\mathbf{E}|\) . \(|\mathbf{E}|\) can range from zero to a maximum of \(|\mathbf{V}|^2 - |\mathbf{V}|\) .

Some graph applications require that a given pair of vertices can have multiple or parallel edges connecting them, or that a vertex can have an edge to itself. However, the applications discussed here do not require either of these special cases. To simplify our graph API, we will assume that there are no duplicate edges.

A graph whose edges are not directed is called an undirected graph , as shown in part (a) of the following figure. A graph with edges directed from one vertex to another (as in (b)) is called a directed graph or digraph . A graph with labels associated with its vertices (as in (c)) is called a labeled graph . Associated with each edge may be a cost or weight . A graph whose edges have weights (as in (c)) is said to be a weighted graph .

Figure 10.2.1: Some types of graphs.

An edge connecting Vertices \(a\) and \(b\) is written \((a, b)\) . Such an edge is said to be incident with Vertices \(a\) and \(b\) . The two vertices are said to be adjacent . If the edge is directed from \(a\) to \(b\) , then we say that \(a\) is adjacent to \(b\) , and \(b\) is adjacent from \(a\) . The degree of a vertex is the number of edges it is incident with. For example, Vertex \(e\) below has a degree of three.

In a directed graph, the out degree for a vertex is the number of neighbors adjacent from it (or the number of edges going out from it), while the in degree is the number of neighbors adjacent to it (or the number of edges coming in to it). In (c) above, the in degree of Vertex 1 is two, and its out degree is one.

A sequence of vertices \(v_1, v_2, ..., v_n\) forms a path of length \(n-1\) if there exist edges from \(v_i\) to \(v_{i+1}\) for \(1 \leq i < n\) . A path is a simple path if all vertices on the path are distinct. The length of a path is the number of edges it contains. A cycle is a path of length three or more that connects some vertex \(v_1\) to itself. A cycle is a simple cycle if the path is simple, except for the first and last vertices being the same.

An undirected graph is a connected graph if there is at least one path from any vertex to any other. The maximally connected subgraphs of an undirected graph are called connected components . For example, this figure shows an undirected graph with three connected components.

A graph with relatively few edges is called a sparse graph , while a graph with many edges is called a dense graph . A graph containing all possible edges is said to be a complete graph . A subgraph \(\mathbf{S}\) is formed from graph \(\mathbf{G}\) by selecting a subset \(\mathbf{V}_s\) of \(\mathbf{G}\) ’s vertices and a subset \(\mathbf{E}_s\) of \(\mathbf{G}\) ‘s edges such that for every edge \(e \in \mathbf{E}_s\) , both vertices of \(e\) are in \(\mathbf{V}_s\) . Any subgraph of \(V\) where all vertices in the graph connect to all other vertices in the subgraph is called a clique .n

A graph without cycles is called an acyclic graph . Thus, a directed graph without cycles is called a directed acyclic graph or DAG .

A free tree is a connected, undirected graph with no simple cycles. An equivalent definition is that a free tree is connected and has \(|\mathbf{V}| - 1\) edges.

10. 1.1.1. Graph Representations ¶

There are two commonly used methods for representing graphs. The adjacency matrix for a graph is a \(|\mathbf{V}| \times |\mathbf{V}|\) array. We typically label the vertices from \(v_0\) through \(v_{|\mathbf{V}|-1}\) . Row \(i\) of the adjacency matrix contains entries for Vertex \(v_i\) . Column \(j\) in row \(i\) is marked if there is an edge from \(v_i\) to \(v_j\) and is not marked otherwise. The space requirements for the adjacency matrix are \(\Theta(|\mathbf{V}|^2)\) .

The second common representation for graphs is the adjacency list . The adjacency list is an array of linked lists. The array is \(|\mathbf{V}|\) items long, with position \(i\) storing a pointer to the linked list of edges for Vertex \(v_i\) . This linked list represents the edges by the vertices that are adjacent to Vertex \(v_i\) .

Here is an example of the two representations on a directed graph. The entry for Vertex 0 stores 1 and 4 because there are two edges in the graph leaving Vertex 0, with one going to Vertex 1 and one going to Vertex 4. The list for Vertex 2 stores an entry for Vertex 4 because there is an edge from Vertex 2 to Vertex 4, but no entry for Vertex 3 because this edge comes into Vertex 2 rather than going out.

Figure 10.2.7: Representing a directed graph.

Both the adjacency matrix and the adjacency list can be used to store directed or undirected graphs. Each edge of an undirected graph connecting Vertices \(u\) and \(v\) is represented by two directed edges: one from \(u\) to \(v\) and one from \(v\) to \(u\) . Here is an example of the two representations on an undirected graph. We see that there are twice as many edge entries in both the adjacency matrix and the adjacency list. For example, for the undirected graph, the list for Vertex 2 stores an entry for both Vertex 3 and Vertex 4.

Figure 10.2.8: Representing an undirected graph.

The storage requirements for the adjacency list depend on both the number of edges and the number of vertices in the graph. There must be an array entry for each vertex (even if the vertex is not adjacent to any other vertex and thus has no elements on its linked list), and each edge must appear on one of the lists. Thus, the cost is \(\Theta(|\mathbf{V}| + |\mathbf{E}|)\) .

Sometimes we want to store weights or distances with each each edge, such as in Figure 10.2.1 (c). This is easy with the adjacency matrix, where we will just store values for the weights in the matrix. In Figures 10.2.7 and 10.2.8 we store a value of “1” at each position just to show that the edge exists. That could have been done using a single bit, but since bit manipulation is typically complicated in most programming languages, an implementation might store a byte or an integer at each matrix position. For a weighted graph, we would need to store at each position in the matrix enough space to represent the weight, which might typically be an integer.

The adjacency list needs to explicitly store a weight with each edge. In the adjacency list shown below, each linked list node is shown storing two values. The first is the index for the neighbor at the end of the associated edge. The second is the value for the weight. As with the adjacency matrix, this value requires space to represent, typically an integer.

Which graph representation is more space efficient depends on the number of edges in the graph. The adjacency list stores information only for those edges that actually appear in the graph, while the adjacency matrix requires space for each potential edge, whether it exists or not. However, the adjacency matrix requires no overhead for pointers, which can be a substantial cost, especially if the only information stored for an edge is one bit to indicate its existence. As the graph becomes denser, the adjacency matrix becomes relatively more space efficient. Sparse graphs are likely to have their adjacency list representation be more space efficient.

Example 10.2.1

Assume that a vertex index requires two bytes, a pointer requires four bytes, and an edge weight requires two bytes. Then, each link node in the adjacency list needs \(2 + 2 + 4 = 8\) bytes. The adjacency matrix for the directed graph above requires \(2 |\mathbf{V}^2| = 50\) bytes while the adjacency list requires \(4 |\mathbf{V}| + 8 |\mathbf{E}| = 68\) bytes. For the undirected version of the graph above, the adjacency matrix requires the same space as before, while the adjacency list requires \(4 |\mathbf{V}| + 8 |\mathbf{E}| = 116\) bytes (because there are now 12 edges represented instead of 6).

The adjacency matrix often requires a higher asymptotic cost for an algorithm than would result if the adjacency list were used. The reason is that it is common for a graph algorithm to visit each neighbor of each vertex. Using the adjacency list, only the actual edges connecting a vertex to its neighbors are examined. However, the adjacency matrix must look at each of its \(|\mathbf{V}|\) potential edges, yielding a total cost of \(\Theta(|\mathbf{V}^2|)\) time when the algorithm might otherwise require only \(\Theta(|\mathbf{V}| + |\mathbf{E}|)\) time. This is a considerable disadvantage when the graph is sparse, but not when the graph is closer to full.

10. 1.2. Graph Terminology Questions ¶

Contact Us | | Privacy | | License    «   9. 12. Hashing Chapter Summary Exercises   ::   Contents   ::   10. 2. Graph Implementations   »

Contact Us | | Report a bug

Graphs and graph representations

• vertices and edges
• directed vs undirected graphs
• labeled graphs
• adjacency and degree
• adjacency-matrix and adjacency-list representations
• paths and cycles
• topological sorting
• more graph problems: shortest paths, graph coloring

A graph is a highly useful mathematical abstraction. A graph consists of a set of vertices (also called nodes ) and a set of edges (also called arcs ) connecting those vertices. There are two main kinds of graphs: undirected graphs and directed graphs . In a directed graph (sometimes abbreviated as digraph ), the edges are directed: that is, they have a direction, proceeding from a source vertex to a sink (or destination ) vertex. The sink vertex is a successor of the source, and the the source is a predecessor of the sink. In undirected graphs, the edges are symmetrical.

Uses of graphs

Graphs are a highly useful abstraction in computer science because so many important problems can be expressed in terms of graphs. We have already seen a number of graph structures: for example, the objects in a running program form a directed graph in which the vertices are objects and references between objects are edges. To implement automatic garbage collection (which discards unused objects), the language implementation uses a algorithm for graph reachability .

• states of games and puzzles, which are vertices connected by edges that are the legal moves in the game,
• state machines, where the states are vertices and the transitions between states are edges,
• road maps, where the vertices are intersections or points along the road and edges are roads connecting those points,
• scheduling problems, where vertices represent events to be scheduled and edges might represent events that cannot be scheduled together, or, depending on the problem, edges that must be scheduled together,
• and in fact, any binary relation ρ can be viewed as a directed graph in which the relationship x ρ y corresponds to an edge from vertex x to vertex y.

What is the value of having a common mathematical abstraction like graphs? One payoff is that we can develop algorithms that work on graphs in general. Once we realize we can express a problem in terms of graphs, we can consult a very large toolbox of efficient graph algorithms, rather than trying to invent a new algorithm for the specific domain of interest.

There are many computational problems over graphs that are not known to be solvable in any reasonable amount of time. In particular, there is a large class of problems known as the NP complete problems that are not known to be efficiently solvable, but are known to be equivalent in complexity. If we could give an efficient algorithm for solving any one of them, then we would have efficient algorithms for all of them.

Vertices and edges

A graph consists of a set of vertices V and a set of edges E. If the graph is directed, the edges E are a set of ordered pairs (u,v) representing an edge with source vertex u and sink vertex v. When drawing graphs, this is usually represented as an arrow from u to v.

If the graph is undirected, then the edges are a set of sets of unordered pairs {u,v}. Alternatively, we can model an undirected graph as a directed graph with edges in both directions; i.e., if (u,v) ∈ E, then (v,u) ∈ E also. When drawing graphs, this is usually represented as a line between u and v without an arrowhead.

In some cases, edges from a vertex to itself or multiple edges between the same pair of vertices may be permitted. But usually the default is not to allow these things unless explicly stated otherwise.

Adjacency and degree

Two vertices v and w are adjacent if they are connected by an edge. The degree of a vertex is the total number of adjacent vertices. In a directed graph, we can distinguish between outgoing and incoming edges. The out-degree of a vertex is the number of outgoing edges and the in-degree is the number of incoming edgs.

The real value of graphs is obtained when we can use them to organize information. Both edges and vertices of graphs can have labels that carry meaning about an entity represented by a vertex or about the relationship between two entities represented by an edge. For example, we might encode information about the population of cities and distances between them as an undirected labeled graph:

Here, the vertices are labeled with a pair containing the name of the city and its population, and the edges are labeled with the distance between the cities.

A graph in which the edges are labeled with numbers is called a weighted graph . Of course, the labels do not have to represent weight; they might stand for distances, or the probability of transitioning from one state to another, or the similarity between two vertices, etc.

Graph representations

There are several ways to represent graphs in a computer program. Which representation is best depends on the application. For example, consider the following weighted directed graph with vertices {0,1,2,3} and directed edges with edge weights shown:

Adjacency matrix

An adjacency matrix represents a graph as a two-dimensional array. Each vertex is assigned a distinct index in {0,1,...,|V|-1}. If the graph is represented by the 2D array m , then the edge (or lack thereof) from vertex i to vertex j is recorded at m[i][j] .

The graph structure, ignoring the weights, can be represented by storing a boolean value at each array index. A directed edge from i to j is represented by a true (T) value in location m[i][j]. If there is no edge there, the value is false. For example, the edges in the example above are represented this matrix:

More compact bit-level representations for the booleans are also possible.

If there is some information associated with each edge, say a weight, we store that information in the corresponding array entry:

The space required by the adjacency matrix representation is O(V 2 ), so adjacency matrices can waste a lot of space if the number of edges |E| is much smaller than O(V 2 ). In particular, a graph with only O(V) edges is said to be sparse . For example, graphs in which either the in-degree or out-degree is bounded by a constant are sparse. Adjacency matrices are not as wasteful when the graphs they represent are dense (i.e., not sparse).

The adjacency matrix representation is time -efficient for some operations. Testing whether there is an edge between two vertices can clearly be done in constant time. However, finding all incoming edges to a given vertex, or finding all outgoing edges, takes time proportional to the number of vertices, even for sparse graphs.

Undirected graphs can also be represented with an adjacency matrix. The matrix will be symmetric around its main diagonal; that is, m[i][j]=m[j][i].

Adjacency list representation

Since sparse graphs are quite common, the adjacency list representation is often preferred. This representation keeps track of the outgoing edges from each vertex, typically as a linked list. For example, the graph above might be represented with the following data structure:

Adjacency lists are asymptotically space-efficient because they only use space proportional to the number of vertices and the number of edges. We say that they require O(V+E) space.

Finding the outgoing edges from a vertex is very efficient in the adjacency list representation too; it requires time proportional to the number of outgoing edges. However, finding the incoming edges to a vertex is not efficient: it requires scanning the entire data structure, requiring O(V+E) time.

When it is necessary to be able to walk forward on outgoing edges and backward on incoming edges, a good approach is to maintain two adjacency lists, one representing the graph as above and one corresponding to the dual (or transposed ) graph in which all edges are reversed. That is, there is a an edge (u,v) in the original graph if and only if there is an edge (v,u) in the transposed graph. Of course, this invariant must be maintained between the two adjacency list representations.

Testing whether there is an edge from vertex i to vertex j requires scanning all the outgoing edges, taking O(V) time in the worse case. If this operation needs to be fast, the linked list can be replaced with a hash table. For example, we might implement the graph using this Java representation, which preserves the asympotic space efficiency of adjacency lists while also supporting queries for particular edges:

Paths and cycles

Following a series of edges from a starting vertex creates a path through the graph, a sequence of alternating vertices and edges beginning and ending with a vertex (v 0 ,e 0 ,v 1 ,e 1 ,...,v n ) where e i = (v i ,v i+1 ) for all 0≤i≤n-1. The length of the path is the number of edges (that is, n). Note that n=0 is possible; this would be a path of length 0 consisting of just a single vertex and no edges. If no vertex appears twice in the path, except that possibly v 0 = v n , the path is called simple . If the first and last vertices are the same, the path is a cycle .

Some graphs have no cycles. For example, linked lists and trees are both examples of graphs in which there are no cycles. They are directed acyclic graphs , abbreviated as DAGs. In trees and linked lists, each vertex has at most one predecessor. In general, vertices of DAGs can have more than one predecessor.

Topological sorting

One use of directed graphs is to represent an ordering constraint on vertices. For example, vertices might represent events, and an edge (u,v) might represent the constraint that u must happen before v.

A topological sort of the vertices is a total ordering of the vertices that is consistent with all edges. That is, if (u,v) is an edge, then u must appear before v in the total ordering. A graph can be topologically sorted if and only if it has no cycles.

Topological sorts are useful for deciding in what order to do things. For example, consider the following DAG expressing what we might call the “men's informal dressing problem”:

A valid plan for getting dressed is a topological sort of this graph. In fact, any topological sort is in principle a workable way to get dressed. For example, the ordering (pants, shirt, belt, socks, tie, jacket, shoes) is consistent with the ordering on all the graph edges. Less conventional strategies are also workable, such as (socks, pants, shoes, shirt, belt, tie, jacket).

Does every DAG have a topological sort? Yes. To see this, observe that every finite DAG must have a vertex with in-degree zero. To find such a vertex, we start from an arbitrary vertex in the graph and walk backward along edges until we reach a vertex with zero in-degree. We know that the walk must generate a simple path because there are no cycles in the graph. Therefore, the walk must terminate because we run out of vertices that haven't already been seen along the walk.

This gives us an (inefficient) way to topologically sort a DAG:

Since finding the 0 in-degree node takes O(V) time, this algorithm takes O(V 2 ) time. We can do better, as we'll see shortly.

Other graph problems

Many problems of interest can be expressed in terms of graphs. Here are a few examples of important graph problems, some of which can be solved efficiently and some of which are intractable!

Reachability

One vertex is reachable from another if there is a path from one to the other. Determining which vertices are reachable from a given vertex is useful and can be done in linear time.

Shortest paths

For example, if a road map is represented as a graph with vertices representing intersections and edges representing road segments, the shortest-path problem can be used to find short routes. There are several variants of the problem, depending on whether one is interested in the distance from a given root vertex or in the distances between all pairs of vertices. If negative-weight edges exist, these problems become harder and different algorithms are needed.

Hamiltonian paths and the traveling salesman problem

The problem of finding the longest simple path between two nodes in a graph is, in general, intractable. It is related to some other important problems. A Hamiltonian path is one that visits every vertex in a graph exactly once. A Hamiltonian cycle is a cycle that visits every vertex exactly once. The ability to determine whether a graph contains a Hamiltonian path or a Hamiltonian cycle would be useful, but in general the best known algorithms for this problem require exponential time.

A weighted version of this problem is the traveling salesman problem (TSP), which tries to find the Hamiltonian cycle with the minimum total weight. The name comes from imagining a salesman who wants to visit every one of a set of cities while traveling the least possible total distance. This problem is at least as hard as finding Hamiltonian cycles and is not known to be solvable in any less than exponential time. However, finding a solution that is within a constant factor (e.g., 1.5) of optimal can be done in polynomial time under some reasonable assumptions. In practice, there exist good heuristics that allow close-to-optimal solutions to TSP even for large problem instances.

Graph coloring

Imagine that we want to schedule exams in k time slots such that no student has two exams at the same time. We can represent this problem using an undirected graph in which the exams are vertices, with the exams v 1 and v 2 connected by an edge if there exists at least one student who needs to take both exams. We can schedule the exams in the k slots if there is a k-coloring of the graph with k colors: a way to assign a color to each vertex with one of k colors such that no two adjacent vertices are assigned the same color. The chromatic number of a graph is the smallest number of colors needed to color it.

There is no known efficient algorithm for k coloring in general. There are some special classes of graphs for which coloring is efficient, and in practice, graph colorings close to optimal can be found, but in general the best known algorithms to solve the problem optimally take exponential time.

Ensure that you are logged in and have the required permissions to access the test.

A server error has occurred. Please refresh the page or try after some time.

An error has occurred. Please refresh the page or try after some time.

Signup and get free access to 100+ Tutorials and Practice Problems Start Now

• Linear Search
• Binary Search
• Ternary Search
• Bubble Sort
• Selection Sort
• Insertion Sort
• Counting Sort
• Bucket Sort
• Basics of Greedy Algorithms

Graph Representation

• Breadth First Search
• Depth First Search
• Minimum Spanning Tree
• Shortest Path Algorithms
• Flood-fill Algorithm
• Articulation Points and Bridges
• Biconnected Components
• Strongly Connected Components
• Topological Sort
• Hamiltonian Path
• Maximum flow
• Minimum Cost Maximum Flow
• Basics of String Manipulation
• String Searching
• Z Algorithm
• Manachar’s Algorithm
• Introduction to Dynamic Programming 1
• 2 Dimensional
• State space reduction
• Dynamic Programming and Bit Masking

Graphs are mathematical structures that represent pairwise relationships between objects. A graph is a flow structure that represents the relationship between various objects. It can be visualized by using the following two basic components:

Nodes: These are the most important components in any graph. Nodes are entities whose relationships are expressed using edges. If a graph comprises 2 nodes $$A$$ and $$B$$ and an undirected edge between them, then it expresses a bi-directional relationship between the nodes and edge.

Edges: Edges are the components that are used to represent the relationships between various nodes in a graph. An edge between two nodes expresses a one-way or two-way relationship between the nodes.

Types of nodes

Root node: The root node is the ancestor of all other nodes in a graph. It does not have any ancestor. Each graph consists of exactly one root node. Generally, you must start traversing a graph from the root node.

Leaf nodes: In a graph, leaf nodes represent the nodes that do not have any successors. These nodes only have ancestor nodes. They can have any number of incoming edges but they will not have any outgoing edges.

Types of graphs

• Undirected: An undirected graph is a graph in which all the edges are bi-directional i.e. the edges do not point in any specific direction.

• Directed: A directed graph is a graph in which all the edges are uni-directional i.e. the edges point in a single direction.

Weighted: In a weighted graph, each edge is assigned a weight or cost. Consider a graph of 4 nodes as in the diagram below. As you can see each edge has a weight/cost assigned to it. If you want to go from vertex 1 to vertex 3, you can take one of the following 3 paths:

• 1 -> 2 -> 3
• 1 -> 4 -> 3

Therefore the total cost of each path will be as follows: - The total cost of 1 -> 2 -> 3 will be (1 + 2) i.e. 3 units - The total cost of 1 -> 3 will be 1 unit - The total cost of 1 -> 4 -> 3 will be (3 + 2) i.e. 5 units

Cyclic: A graph is cyclic if the graph comprises a path that starts from a vertex and ends at the same vertex. That path is called a cycle. An acyclic graph is a graph that has no cycle.

A tree is an undirected graph in which any two vertices are connected by only one path. A tree is an acyclic graph and has N - 1 edges where N is the number of vertices. Each node in a graph may have one or multiple parent nodes. However, in a tree, each node (except the root node) comprises exactly one parent node.

Note : A root node has no parent.

A tree cannot contain any cycles or self loops, however, the same does not apply to graphs.

Graph representation

You can represent a graph in many ways. The two most common ways of representing a graph is as follows:

Adjacency matrix

An adjacency matrix is a VxV binary matrix A . Element $$A_{i,j}$$ is 1 if there is an edge from vertex i to vertex j else $$A_{i,j}$$ is 0.

Note : A binary matrix is a matrix in which the cells can have only one of two possible values - either a 0 or 1.

The adjacency matrix can also be modified for the weighted graph in which instead of storing 0 or 1 in $$A_{i,j}$$ , the weight or cost of the edge will be stored.

In an undirected graph, if $$A_{i,j}$$ = 1, then $$A_{j,i}$$ = 1. In a directed graph, if $$A_{i,j}$$ = 1, then $$A_{j,i}$$ may or may not be 1.

Adjacency matrix provides constant time access (O(1) ) to determine if there is an edge between two nodes. Space complexity of the adjacency matrix is O($$V^2$$) .

The adjacency matrix of the following graph is: i/j : 1 2 3 4 1 : 0 1 0 1 2 : 1 0 1 0 3 : 0 1 0 1 4 : 1 0 1 0

The adjacency matrix of the following graph is:

i/j : 1 2 3 4 1 : 0 1 0 0 2 : 0 0 0 1 3 : 1 0 0 1 4 : 0 1 0 0

Consider the directed graph given above. Let's create this graph using an adjacency matrix and then show all the edges that exist in the graph.

Input file 4 $$\hspace{2cm}$$ // nodes 5 $$\hspace{2cm}$$//edges 1 2 $$\hspace{1.5cm}$$ //showing edge from node 1 to node 2 2 4 $$\hspace{1.5cm}$$ //showing edge from node 2 to node 4 3 1 $$\hspace{1.5cm}$$ //showing edge from node 3 to node 1 3 4 $$\hspace{1.5cm}$$ //showing edge from node 3 to node 4 4 2 $$\hspace{1.5cm}$$ //showing edge from node 4 to node 2

There is an edge between 3 and 4.

There is no edge between 2 and 3.

Adjacency list

The other way to represent a graph is by using an adjacency list. An adjacency list is an array A of separate lists. Each element of the array A i is a list, which contains all the vertices that are adjacent to vertex i.

For a weighted graph, the weight or cost of the edge is stored along with the vertex in the list using pairs. In an undirected graph, if vertex j is in list $$A_{i}$$ then vertex i will be in list $$A_{j}$$ .

The space complexity of adjacency list is O(V + E) because in an adjacency list information is stored only for those edges that actually exist in the graph. In a lot of cases, where a matrix is sparse using an adjacency matrix may not be very useful. This is because using an adjacency matrix will take up a lot of space where most of the elements will be 0, anyway. In such cases, using an adjacency list is better.

Note: A sparse matrix is a matrix in which most of the elements are zero, whereas a dense matrix is a matrix in which most of the elements are non-zero.

Consider the same undirected graph from an adjacency matrix. The adjacency list of the graph is as follows:

Consider the same directed graph from an adjacency matrix. The adjacency list of the graph is as follows:

A1 → 2 A2 → 4 A3 → 1 → 4 A4 → 2

Consider the directed graph given above. The code for this graph is as follows:

4 $$\hspace{2cm}$$ // nodes 5 $$\hspace{2cm}$$ //edges 1 2 $$\hspace{1.5cm}$$ //showing edge from node 1 to node 2 2 4 $$\hspace{1.5cm}$$ //showing edge from node 2 to node 4 3 1 $$\hspace{1.5cm}$$ //showing edge from node 3 to node 1 3 4 $$\hspace{1.5cm}$$ //showing edge from node 3 to node 4 4 2 $$\hspace{1.5cm}$$ //showing edge from node 4 to node 2

• Adjacency list of node 1: 2
• Adjacency list of node 2: 4
• Adjacency list of node 3: 1 --> 4
• Adjacency list of node 4: 2

• An alphabet
• A special character
• Minimum 8 characters

A password reset link will be sent to the following email id

• DS Tutorial
• DS Introduction
• DS Algorithm
• Asymptotic Analysis
• DS Structure

DS Linked List

• Linked List
• Types of Linked List

Singly Linked List

Doubly linked list, circular linked list, circular doubly list.

• Skip list in DS
• Array Implementation
• Linked List Implementation
• Types of Queues
• Array Representation
• Linked List Representation
• Circular Queue
• Priority Queue

Binary Tree

Binary search tree.

• Red-black tree
• Graph Implementation
• BFS Algorithm
• DFS Algorithm
• Spanning Tree
• a)Prim's Algorithm
• b)Kruskal's Algorithm

DS Searching

• Linear Search
• Binary Search
• Bubble Sort
• Bucket Sort
• Counting Sort
• Insertion Sort
• Selection Sort
• Bitonic Sort
• Cocktail Sort

Differences

• Linear vs non-linear
• Array vs linked list
• Stack vs queue
• Linear vs Circular Queue
• Linear Search vs Binary Search
• Singly Linked List vs Doubly Linked List
• Binary vs Binary Search Tree
• Tree vs Graph
• Binary Search tree vs AVL tree
• Red Black Tree vs AVL tree
• B tree vs B+ tree
• Quick Sort vs Merge Sort
• Stack vs Heap
• Bubble sort vs. Selection sort
• Stack vs Array
• Full Binary Tree vs Complete Binary Tree
• Binary Tree vs B Tree
• Primitive vs non-primitive data structure
• Data types vs data structure
• Trie Data Structure
• Heap Data Structure
• Fundamental of the DS
• Preorder Traversal
• Tree Traversal
• Implementation of Queue using Stacks
• Implementation of Stack using Queue
• Binomial Heap
• Postorder Traversal
• Sparse Matrix
• Detect loop in a Linked list
• Inorder Traversal
• Convert Infix to Postfix notation
• Convert infix to prefix notation
• Conversion of Prefix to Postfix expression
• Conversion of Postfix to Prefix expression
• Remove the loop in a Linked List
• Implement two stacks in an array
• Reverse a stack using recursion
• Detect cycle in a directed graph
• Optimal Binary Search Tree
• Priority Queue using Linked list
• Balanced Binary Search Tree
• Boundary Traversal of Binary tree
• Diagonal Traversal of Binary Tree
• Vertical Traversal of a Binary tree
• Graph Algorithms
• Time Complexity of Sorting Algorithms
• Applications of Stack in Data Structure
• Dictionary Data Structure
• Structured Data and Unstructured Data
• List Data Structure
• Types of Tree in Data Structure
• Abstract data type in data structure
• Disjoint set data structure
• Dynamic Data Structure
• Hash Function in Data Structure
• Complete Binary Tree
• Threaded Binary Tree
• Diameter of Binary Tree
• Height of Binary Tree
• Inorder Tree Traversal without Stack
• Enumeration of Binary Trees
• Maximum Width of a Binary Tree
• Types of Graph in Data Structure
• Primitive Data Type
• Semi-Structured Data
• Advance Data Structures
• Sort an Array of 0's, 1's, and 2's
• Stock Span Problem
• Implementation of Deque by Circular Array
• Rotate Operation in Linked List
• Subarray with given sum
• Self-organizing List
• Unrolled Linked List
• Types of Sparse Matrices
• Application of Linked List
• Topological Sorting
• Ternary Search Tree
• Treap Data Structure
• Quicksort on Doubly Linked List
• Inversion count
• Expression tree in DS
• Garbage Collection in DS
• Merge Sort on Doubly Linked List
• Sort Stack using Recursion
• LIFO Approach in data structure
• Big O Notation in DS
• Binary Tree Traversal in DS
• Queue Operations in DS
• What is a Non-Linear Data Structure
• FIFO Approach in data structure
• What are connected graphs in data structure
• Which Python data structure is immutable
• Which data structure is used by map
• What is iteration in data structure
• What are linear search and binary search in data structure
• Hash Table vs STL Map
• Recaman's Sequence
• Maximum area rectangle created by selecting four sides from an array
• Maximum number of distinct nodes in a root-to-leaf path
• Hashing - Open Addressing for Collision Handling
• Introduction to Hashing
• Separate chaining for Collision Handling
• Check if a given array contains duplicate elements within k distance from each other
• Given an array A[] and a number x, check for pair in A[] with sum as x (aka Two Sum)
• Find number of Employees Under every Manager
• Union and Intersection of two Linked Lists
• Kth Largest element in an array
• Sort an almost-sorted, k-sorted or nearly-sorted array
• Fibonacci Heap
• Find whether an array is subset of another array
• Print a Binary Tree in Vertical Order
• Tournament Tree (Winner Tree)
• Lazy Propagation in Segment Tree
• Segment Tree - Range Minimum Query
• Segment Tree - Sum of given Range
• 2-3 Trees (Search, Insertion, and Deletion)
• Print kth least significant bit of a number
• Add two numbers represented by linked lists
• Adding one to the number represented as array of digits
• Find precedence characters form a given sorted dictionary
• Check if any anagram of a string is palindrome or not
• Minimum Insertions to form a Palindrome
• Allocate Minimum Number of Pages
• Assembly Line Scheduling
• Breadth First Search or BFS for a Graph
• Find an element in array such that sum of the left array is equal to the sum of the right array
• Bridges in a Graph
• Bubble Sort in JavaScript
• Burn the Binary tree from the Target node
• Lowest Common Ancestor in a Binary Search Tree
• Types of Hash Functions in C
• Implement Dynamic Deque using Templates Class and a Circular Array
• Iterative Depth First Traversal of Graph
• Linked List Data Structure in C++ With Illustration
• Reverse a Linked List in Groups of Given Size
• Reverse Alternate K nodes in a Singly Linked List
• When should I use a List vs a LinkedList
• Why is deleting in a Singly Linked List O(1)
• Construct Full Binary Tree using its Preorder Traversal and Preorder Traversal of its Mirror Tree
• Find Relative Complement of two Sorted Arrays
• Handshaking Lemma and Interesting Tree Properties -DSA
• How to Efficiently Implement kStacks in a Single Array
• Write C Functions that Modify Head Pointer of a Linked List
• Introduction to Ant Colony Optimization
• What is Array
• The practical Byzantine Fault Tolerance (pBFT)
• Applications of Queue Data Structure
• Symmetric Binary Tree
• AVL Tree Advantages
• AVL Tree Time Complexity
• Merge Two Binary Trees
• Stack Operations in Data Structure
• Self-Balancing Binary Search Trees
• Sliding Window Maximum (Maximum of all Subarrays of size K)
• AVL Trees Operations
• Limitations of Stack in Data Structures
• Representation of stack in data structure
• Advantages of Threaded Binary Tree
• Serialize and Deserialize a Binary Tree
• Application of Binary Tree
• AVL Tree Applications
• B Tree Visualization
• Properties of AVL Trees
• Push and Pop Operation in Stack in Data Structure
• Binary Search Tree Implementation
• Find Maximum Sum by Replacing the Subarray in Given Range
• Find The Number N, Where (N+X) Divisible By Y And (N-Y) Divisible By X
• Find Values of P and Q Satisfying the Equation N = P^2.Q
• What is the Balance Factor of AVL Tree
• AVL Tree Implementation in Golang
• Concatenation of two Linked Lists in O(1) time
• Find Minimum Area of Rectangle Formed from Given Shuffled Coordinates
• Find the Length of Maximum Path in Given Matrix for Each Index
• How to Parse an Array of Objects in C++ Using RapidJson
• Largest BST in Binary Tree
• How to Print String Literal and Qstring With Qdebug in C++
• Properties of Binary Tree
• Right View of Binary Tree
• Strict Binary Tree
• Difference between Comb Sort and Shell Sort
• Full Binary Tree
• Left View of a Binary Tree
• Level order Traversal in a Binary Tree
• Lowest Common Ancestor of a Binary Tree
• Top View of a Binary Tree
• Types of Binary Trees
• B Tree Insertion
• Evaluation of a Postfix notation
• B+ Tree Insertion
• Bottom View of a Binary Tree
• AVL Tree Program in C
• B Tree Applications
• B Tree Properties
• How to Search, Insert, and Delete in an Unsorted Array
• Count Non-Leaf Nodes in a Binary Tree
• Get the Level of a Given Key in a Binary Tree
• Double Ended Priority Queue
• B+ Tree Deletion
• Checking for the Mirror Images in the Binary Trees
• Get a Parent Binary Tree
• Get All Descendants of the Binary Tree Element
• Flatten Binary Tree to Linked List
• Formula to Find a Level of the Node in a Binary Tree
• Substring with Maximum Number of Vowels of Given Length (k)
• Flatten Binary Tree to Sorted Linked List
• Floor and Ceiling in Binary Search Tree
• Find Level in a Binary Tree with Max Sum
• Find kth Smallest Element in a Binary Search Tree
• Find Next Greater Element in Binary Tree
• Hashing in Data Structure
• Primitive Data Structure
• Find if Binary Tree Satisfies Balanced Height Property
• Find the Largest Perfect Binary Tree in a Given Tree
• Find Immediate Parents of Two Nodes in a Binary Tree
• Applications, Advantages and Disadvantages of Circular Doubly linked List
• Sorting Techniques in Data Structures
• Find Clockwise Array in Binary Search Tree
• Find Duplicate Subtrees in Binary Tree
• Find the Index of the Number Using a Binary Tree
• Find the In-Order Successor of a Node in a Binary Tree
• Reversing a Queue
• Different Types of Stack Operations
• Time Complexity in Data Structure
• Arrays are best Data Structure
• Dynamic memory allocation in Data Structure
• Application of Data Structure
• Applications of Tree in Data Structure
• How to Check if a Binary Number is Divisible by 3
• Stock Buy and Sell Problem
• Find Minimum in Rotated Sorted Array
• Interpolation Search vs. Binary Search
• Boggle (find all possible words in a board of characters)
• Difference Between Prim's and Kruskal's algorithm
• Interpolation Search
• Quick Sort Using Hoare's Partition
• Longest common substring
• Longest Repeated Substring
• Substring Check
• Clone a Binary Tree with Random Pointers
• How to efficiently implement k stacks in a single array
• Kasai's algorithm for construction of LCP array from Suffix array
• Strassen's Matrix Multiplication
• suffix array introduction
• Suffix Array nLogn Algorithm
• Suffix tree introduction
• Binary indexed tree
• Given a n x n square matrix, find the sum of all sub-squares of size k x k
• Inplace MxN size matrix transpose
• longest palindrome substring
• Maximum Size Square Sub-matrix with all 1s
• Maximum Sum Rectangle in a 2D Matrix
• Printing All Elements in Sorted Order from Row and Column Wise Sorted Matrix
• Arraylist vs linked list
• Diameter of an N-ary Tree
• Generic Trees (N-ary Trees)
• Level Order Traversal of N-ary Tree
• Mirror of n-ary Tree
• Serialize and Deserialize an N-ary Tree
• Sum of all elements of N-ary Tree
• The Great Tree-List Recursion Problem
• Two dimensional Binary Indexed Tree or Fenwick Tree
• Binary Indexed Tree Range Updates and Point Queries
• Binary Indexed Tree Range Updates and Range Queries
• Closest greater or same value on left side for every element in array
• Construct an array from its pair-sum array
• Equilibrium index of an array
• Fermat's Factorization Method in Java
• Find a triplet that sum to a given value in an array
• Find k numbers with most occurrences in the given array
• Find maximum value of Sum(i*arr[i]) with only rotations on given array allowed
• Handshaking Lemma and Interesting Tree Properties
• Implementation of Dynamic Segment Trees with Poly Hash Tables
• Majority Element
• Maximum equilibrium sum in an array
• Maximum profit by buying and selling a share at most twice
• Median in a stream of integers (running integers)
• Merge Sort Tree for Range Order Statistics
• Merge two sorted arrays with O(1) extra space
• Minimum increment by k operations to make all elements equal
• Minimum number of jumps to reach end
• MO's Algorithm
• Search in a row-wise and column-wise sorted matrix
• Smallest subarray with sum greater than a given value
• Sparse Table
• Square Root (Sqrt) Decomposition Algorithm
• Two Pointers Technique
• Compressed segment trees and merging sets in O(N*logN)
• Intersection of Linked List
• Intersection Point in Y shaped linked list
• Make Array Zero By Subtracting Equal Amounts In Java
• Maximum Sum Pair with Equal Highest Digits
• Minimum Possible value of |ai + aj - k| for given array and k
• Tango Tree Data Structure
• Check if two arrays are equal or not
• Construct BST from its given level order traversal
• Elements to be added so that all elements of a range are present in the array
• Find Missing Elements in Range
• K-th Largest Sum Contiguous Subarray
• Minimum number of subsets with distinct elements
• Minimum product of k integers in an array of positive integers
• The non-overlapping sum of two sets
• Palindrome substring queries
• The sum of Elements Between k1th and k2th smallest elements
• Print Matrix in a Snake Pattern
• An Interesting Method to Generate Binary Numbers from 1 to n
• Circular List Application
• Deleting a Node in a Linked List
• Diameter of a Binary Tree
• Find distance between two nodes of a Binary Search Tree
• Inorder Tree Traversal without Recursion
• Inorder Tree Traversal without recursion and stack!
• Maximum product of indexes of next greater on left and right
• Print Left View of a Binary Tree
• Remove all leaf nodes from the binary search tree
• Sort a stack using a temporary stack
• Split a Circular List into 2 Halves
• Check given array of size n can represent BST of n levels or not
• Construct a linked list from 2D matrix
• In place, convert BST into a Min-Heap
• Polish and Reverse Polish Notation
• Suffix Trees in data structure
• Weight Balanced Binary Tree
• Transform a BST to greater sum tree
• Vertical order traversal of Binary Tree using Map
• Application of heap tree
• Define Abstract Data Type in Data Structure
• Detect and Remove Loop in a Linked List
• Difference Between a Tree and a Forest in Data Structures
• Difference between bubble sort and merge sort
• Difference between merge sort and quick sort
• Explain double ended queue in detail
• Find the median from running data stream
• Flattening a Linked List
• Generate All Subarrays
• Heap memory vs. stack memory
• Huffman encoding
• Huffman Tree in Data Structure
• Implementation of Graph in JavaScript
• K-D Tree in Data Structures
• Knapsack Problem in Data Structure
• Largest Sum Contiguous Subarray (Kadane's Algorithm)
• Multiway Trees in Data Structures
• Optimal binary search tree in data structure
• polynomial addition in data structure
• Postfix deferred queue
• Properties of tree in data structure
• Recurrence Relation of Merge Sort
• Recursive Bubble Sort
• RSS linked list
• Search in a Rotated Sorted Array
• Sort an array of 0s, 1s and 2s | Dutch National Flag problem
• Assign directions to edges so that the directed graph remains acyclic
• Dependency Graph
• Diameter of an N-ary tree
• Height of n-ary tree if parent array is given
• Introduction to Heavy Light Decomposition
• LCA in a binary tree using RMQ
• Number of Siblings of a given node in n-arr tree
• Number of ways to traverse an N-arr
• XOR Linked List - A Memory Efficient Doubly Linked List
• Callback Queue
• Inorder Predecessor and Successor in a Binary Search Tree
• What is Internal Sorting
• Block Swap Algorithm for Array Rotation in Python
• CHECK FOR BALANCED BRACKETS IN AN EXPRESSION (WELL FORMEDNESS)
• Count pairs from two BSTs whose sum is equal to given value x
• Counting Inversions Problem in Data Structure
• Differences between Insertion Sort and Selection Sort
• LEFTIST TREE / LEFTIST HEAP
• Find if there is a triplet in a balanced bst that adds to zero
• Find the Maximum English Letter Present in Both Lowercase and Uppercase
• K-way Merge Sort
• Perfect Binary Trees
• Reverse Sort
• Scapegoat Trees
• Stack Organisation
• Time Complexity of using heap
• Two-way merge sort
• Validity of a given Tic-Tac-Toe board configuration
• Weighted Prefix Search
• Binary Tree to CDLL
• Check if a Binary Tree is a Subtree of Another Binary Tree
• Check if the Given String of Words can be Formed from Words Present in the Dictionary
• Count sort vs bucket sort
• FIFO vs LIFO approach in Programming
• If you are given two traversal sequences, can you construct the binary tree
• Linked List Deletion (Deleting a key at a given position)
• Mastering Bracket Problems for Competitive Programming
• Merge Overlapping Intervals
• MIRROR OF MATRIX ACROSS DIAGONAL
• Pair of strings having longest common prefix of maximum length in given array
• Print all Possible Combinations of Words from the Dictionary using Trie
• Segment Tree (Range Maximum Query with Node Update)
• Tree Vertex Splitting in data structure
• Why is Binary Heap Preferred over BST for Priority Queue
• Arrange Consonants and Vowels in a linked list
• Copy a linked list with next and arbit pointer
• Kahn's Algorithm vs DFS Approach: A Comparative Analysis
• Minimum flip required to make Binary Matrix symmetric
• Sorted insert for circular linked list
• C++ Program for Arranging Single Linked List in Alternate Odd and Even Nodes Order
• Reservoir sampling in C++
• 0/1 Knapsack using Least Cost Branch and Bound
• Merge K Sorted Linked Lists using Min Heap
• Number of elements greater than K in the range L to R using Fenwick Tree (Offline queries)
• Detect Cycle in Graph using DSU
• Merkle Tree and Hash Chain Data Structures with a difference
• Create a matrix with alternating rectangles of O and X
• Find the first non-repeating character from a stream of characters
• Find the first circular tour that visits all petrol pumps
• Find the tasks completed by soldiers based on their ranks
• Numbsubarrayer of elements less than or equal to a given number in a given
• Queries to add, remove and return the difference of maximum and minimum
• Time Complexity of building a heap
• Build linear type suffix
• Count of Valid Splits in a String
• Delete all occurrences of a given key in a linked list
• Design a data structure that supports insert, delete, search and getRandom in constant time
• Find the largest subarray with 0 sum
• Free Tree in Data Structures
• How to insert Strings into an AVL Tree
• Longest Consecutive Subsequence
• Merge two binary Max Heaps
• Secure Message Encoding
• Sort an almost sorted array
• Tree of Space - Locking and Unlocking N-Ary Tree
• Triply Linked list
• COUNT OF ZEROES
• Design a Chess Game
• Design and Implement Special Stack Data Structure
• Enhancing Password Strength
• Enumeration of Binary Tree
• Eulerian and Hamiltonian path
• Fair Array Removal Indices
• Find the Absolute Difference between the Right View Sum of two Binary Trees
• Find the number of colored nodes according to given queries in a full Binary Tree
• Finding Minimum Steps in Special Binary Tree
• Finding the Largest Multiple of Three
• Flatten a binary tree into linked list
• General Tree (Each node can have arbitrary number of children) Level Order Traversal
• Generating the Maximum Number from Two Arrays
• Hashing and its Applications
• Islands in a graph using BFS
• Iterative Letter Combinations of a Phone Number
• Maximize Total Score
• PERMUTED ROWS IN A MATRIX
• Remove extra edge from a BST
• Van Emde Boas Tree
• Which Minimum Spanning Tree Algorithm is better
• Ackermann Function
• BINARY TO SYMMETRIX
• INPLACE MATRIX TRANSPOSE
• Print all words matching a pattern in CamelCase Notation Dictionary
• Reduce the string by removing K consecutive identical characters
• Subtraction in Linked List
• TRANSITIONS OF MATRIX
• Blending vs Stacking
• Bloom Filters
• Count Array Pairs Divisible by k
• Counting Beautiful Numbers in a Specified Range
• Find the Closest Palindrome
• Minimizing water collection distance in javaT village
• Minimum Array Length After Pair Removals
• Nth even Fibonacci Sequence
• Persistent Data Structure
• Queue for Competitive Programming
• Recursively remove all adjacent duplicates
• Remove the letter to equalize the frequency
• Chocolate Distribution Problem
• Find out the person who got the ticket last problem in queue
• Product Array Puzzle
• MCQs on backtracking
• Design a data structure that supports insert, delete, search, and getRandom in constant time
• Print the frequency of each character in Alphabetical order
• Check if a queue can be sorted into another queue using a stack
• Auto-complete feature using Trie
• Connect nodes at same level
• Construct Tree from Given Inorder and Preorder Traversals
• Decimal Equivalent of Binary Linked List
• How do you implement Stack using Priority Queue or Heap
• Introduction to Monotonic Stacks
• Minimum Initial Points to Reach Destination
• Print Ancestors of a given node in Binary Tree
• Priority Queue using Doubly Linked List
• Shortest distance between two cells in a matrix or grid
• Sort an Array in Wave Form
• Burn the binary tree starting from the target node
• Check for possible paths in the 2D Matrix
• Find Triplets with zero-sum
• Print a Given Matrix in Spiral form
• Alien Dictionary problem in dsa
• Array Pair Sum Divisibility Problem
• DIFFERENCE BETWEEN GREEDY AND DIVIDE AND CONQUER
• How do you check if a given array represents a heap
• LINKED LIST REVERSE
• MAXIMUM SIZE RECTANGLE
• Priority queue of pairs in C++ with ordering by first and second element
• Reversing Individual Words and Unveiling the Secrets of Histograms
• Sliding SubArray Beauty
• Two Pointer Technique
• UGLY NUMBERS IN DSA
• Check for Balanced Brackets in an expression
• Largest Number After Digit Swaps By Parity
• Minimize Deviation In Array
• Print a given matrix in spiral form
• Print unique rows in a given Boolean matrix
• Restrictive Candy Crush
• Search in a row wise and column wise sorted matrix
• Stacked Bar Chart
• Search Query Auto Complete
• Applications of the greedy algorithm
• Applications, Advantages and Disadvantages of Arrays
• Applications, Advantages and Disadvantages of Queue
• Applications, Advantages and Disadvantages of Stacks
• Floor and Ceil from a BST
• India Stack
• Next Higher Palindromic Numbers using the Same Set of Digits
• QuickSort on Singly Linked List
• Reverse a Number using Stacks
• Stack Pointer
• What is a K-connected Graph
• Append K Integers with Minimal Sum Problem
• Circular Linked Lists Introduction and Application
• Detect cycle in an undirected graph in C++
• Find the maximum number of marked indices problem
• Generalized Suffix Tree
• Interval Tree
• Maximum Number of Tasks Assignment Problem
• Merge K Sorted Lists
• Triplet sum closest to given number
• Apply Operations To Maximize Frequency Score
• Difference between malloc and realloc
• Merge Sort on Singly Linked Lists
• Minimum Number Of Frogs Croaking
• Total Distance Travelled
• X Of A Kind In A Deck Of Cards
• Applications, Advantages and Disadvantages of Linked List
• Balls rolling in the maze
• Destroy Sequential Targets
• Difference Between Push and Pop in Stack
• Dynamic Programming (DP) on Grids
• Find all good strings problem in Data Structure
• Find Itinerary from a given list of tickets
• Maximum Deletions on a String
• Reversal algorithm for Array rotation
• Reverse Pairs Problem in Data Structure
• String Hashing using the Polynomial Rolling Hash Function
• Trapping of rainwater problem in Data Structure
• What Does Big O(N^2) Complexity Mean
• How to handle duplicates in Binary Search Tree
• Optimal cell in matrix to collect maximum coins
• Maximizing Chocolates in Grid using 2 robots
• Interleave the first half of the queue with the second half
• The sum of all elements between k1'th and k2'th smallest elements
• Check Matrix Transformation by Flipping Sub-Matrices along the Principal or Anti-Diagonal
• DFS for an n-ary Tree(Acyclic Graph) Represented as an Adjacency List
• Difference Between Counting Sort and Bucket Sort
• Internal Data Structures and Time Complexity Table of All the C++ STL Containers
• K Centres Problem (Greedy Approximate Algorithm)
• Left Rotation and Right Rotation of a String
• Merge Two Sorted Linked Lists
• Move all Zeroes to End of Array
• Number of flips to make binary string alternate
• Program to Reveal the Positions in Minesweeper
• Tarjan's Algorithm to Find Strongly Connected Components
• Difference between big o and big theta ? and big omega ? notations
• Data Structure MCQ
• Advanced DS MCQ
• Insertion at beginning
• Insertion at end
• Insertion after specified node
• Deletion at beginning
• Deletion at end
• Deletion after specified node
• Deletion of node having given data
• Deletion at the end
• Pre-order Traversal
• In-order Traversal
• Post-order Traversal
• Searching in BST
• Insertion in BST
• Deletion in BST
• Insertion in AVL Tree
• a)LL Rotation
• b)LR Rotation
• c)RL Rotation
• d)RR Rotation
• Deletion in AVL Tree

Latest Courses

Javatpoint provides tutorials and interview questions of all technology like java tutorial, android, java frameworks

Contact info

G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India

[email protected] .

Interview Questions

Online compiler.

• Heap Data Structure
• Implementing Heaps
• B Trees (M-way Tree)
• Introduction to Graphs
• Graph Representations

Graph Representations - Adjacency Matrix and List

There are two ways in which we represent graphs, these are:

Adjacency Matrix

Adjacency list.

Both these have their advantages and disadvantages. In this tutorial, we will cover both of these graph representation along with how to implement them.

Adjacency matrix representation makes use of a matrix (table) where the first row and first column of the matrix denote the nodes (vertices) of the graph. The rest of the cells contains either 0 or 1 (can contain an associated weight w if it is a weighted graph).

Each row X column intersection points to a cell and the value of that cell will help us in determining that whether the vertex denoted by the row and the vertex denoted by the column are connected or not. If the value of the cell for v1 X v2 is equal to 1, then we can conclude that these two vertices v1 and v2 are connected by an edge, else they aren't connected at all.

Consider the given graph below:

The graph shown above is an undirected one and the adjacency matrix for the same looks as:

The above matrix is the adjacency matrix representation of the graph shown above. If we look closely, we can see that the matrix is symmetric. Now let's see how the adjacency matrix changes for a directed graph.

For the directed graph shown above the adjacency matrix will look something like this:

Implementation of Adjacency Matrix

The structure ( constructor in Java ) for the adjacency matrix will look something like this:

It should also be noted that we have two class-level variables, like:

We have a constructor above named AdjacencyMatrix which takes the count of the number of the vertices that are present in the graph and then assigns our global vertex variable that value and also creates a 2D matrix of the same size. Now since our structure part is complete, we are simply left with adding the edges together, and the way we do that is:

In the above addEdge function we also assigned 1 for the direction from the destination to the start node, as in this code we looked at the example of the undirected graph, in which the relationship is a two-way process. If it had been a directed graph, then we can simply make this value equal to 0, and we would have a valid adjacency matrix.

Now the only thing left is to print the graph.

The entire code looks something like this:

The output of the above looks like:

Adjacency Matrix : 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0

In the adjacency list representation, we have an array of linked-list where the size of the array is the number of the vertex (nodes) present in the graph. Each vertex has its own linked-list that contains the nodes that it is connected to.

Consider the graph shown below:

The above graph is an undirected one and the Adjacency list for it looks like:

The first column contains all the vertices we have in the graph above and then each of these vertices contains a linked list that in turn contains the nodes that each vertex is connected to. For a directed graph the only change would be that the linked list will only contain the node on which the incident edge is present.

The above graph is a directed one and the Adjacency list for this looks like:

Implementation of Adjacency List

The structure (constructor in Java) for the adjacency list will look something like this:

The above constructor takes the number of vertices as an argument and then assigns the class level variable this value, and then we create an array of LinkedList of the size of the vertices present in the graph. Finally, we create an empty LinkedList for each item of this array of LinkedList.

Now we have laid the foundations and the only thing left is to add the edges together, we do that like this:

We are taking the vertices from which an edge starts and ends, and we are simply inserting the destination vertex in the LinkedList of the start vertex and vice-versa (as it is for the undirected graph).

Node 0 is connected to: 1 Node 1 is connected to: 2 0 Node 2 is connected to: 3 1 Node 3 is connected to: 2

• We learned how to represent the graphs in programming, via adjacency matrix and adjacency lists.
• ← Introduction to Graphs ← PREV
• Hash Table → NEXT →

Critical Interpretation of Arguments using Graphs and Representations

• Hanadi Mardah
• Department of Computer Science

Student thesis : Phd

• Argumentation structure; Waltonâ??s classification scheme; Argument mining; Argumentation graphs; Visualisation graphs, Graphs interaction

File : application/pdf, -1 bytes

Type : Thesis

• Interview Problems on Graph
• Practice Graph
• MCQs on Graph
• Graph Tutorial
• Graph Representation
• Graph Properties
• Types of Graphs
• Graph Applications
• BFS on Graph
• DFS on Graph
• Graph VS Tree
• Transpose Graph
• Dijkstra's Algorithm
• Minimum Spanning Tree
• Prim’s Algorithm
• Topological Sorting
• Floyd Warshall Algorithm
• Strongly Connected Components
• Advantages & Disadvantages

Introduction to Graph Data Structure

Graph Data Structure is a non-linear data structure consisting of vertices and edges. It is useful in fields such as social network analysis, recommendation systems, and computer networks. In the field of sports data science, graph data structure can be used to analyze and understand the dynamics of team performance and player interactions on the field.

Table of Content

What is Graph Data Structure?

Components of graph data structure.

• Types Of Graph Data Structure
• Representation of Graph Data Structure
• Adjacency Matrix Representation of Graph Data Structure
• Adjacency List Representation of Graph
• Basic Operations on Graph Data Structure
• Difference between Tree and Graph
• Real-Life Applications of Graph Data Structure
• Advantages of Graph Data Structure
• Disadvantages of Graph Data Structure
• Frequently Asked Questions(FAQs) on Graph Data Structure

Graph is a non-linear data structure consisting of vertices and edges. The vertices are sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph. More formally a Graph is composed of a set of vertices( V ) and a set of edges( E ). The graph is denoted by G(V, E).

Imagine a game of football as a web of connections, where players are the nodes and their interactions on the field are the edges. This web of connections is exactly what a graph data structure represents, and it’s the key to unlocking insights into team performance and player dynamics in sports.

• Vertices: Vertices are the fundamental units of the graph. Sometimes, vertices are also known as vertex or nodes. Every node/vertex can be labeled or unlabelled.
• Edges: Edges are drawn or used to connect two nodes of the graph. It can be ordered pair of nodes in a directed graph. Edges can connect any two nodes in any possible way. There are no rules. Sometimes, edges are also known as arcs. Every edge can be labelled/unlabelled.

Types Of Graphs in Data Structure and Algorithms

1. null graph.

A graph is known as a null graph if there are no edges in the graph.

2. Trivial Graph

3. Undirected Graph

A graph in which edges do not have any direction. That is the nodes are unordered pairs in the definition of every edge. 

4. Directed Graph

A graph in which edge has direction. That is the nodes are ordered pairs in the definition of every edge.

5. Connected Graph

The graph in which from one node we can visit any other node in the graph is known as a connected graph. 

6. Disconnected Graph

The graph in which at least one node is not reachable from a node is known as a disconnected graph.

7. Regular Graph

The graph in which the degree of every vertex is equal to K is called K regular graph.

8. Complete Graph

9. Cycle Graph

The graph in which the graph is a cycle in itself, the minimum value of degree of each vertex is 2. 

10. Cyclic Graph

A graph containing at least one cycle is known as a Cyclic graph.

11. Directed Acyclic Graph

A Directed Graph that does not contain any cycle. 

12. Bipartite Graph

A graph in which vertex can be divided into two sets such that vertex in each set does not contain any edge between them.

13. Weighted Graph

•   A graph in which the edges are already specified with suitable weight is known as a weighted graph. 
•  Weighted graphs can be further classified as directed weighted graphs and undirected weighted graphs. 

Representation of Graph Data Structure:

There are multiple ways to store a graph: The following are the most common representations.

• Adjacency Matrix
• Adjacency List

Adjacency Matrix Representation of Graph Data Structure:

In this method, the graph is stored in the form of the 2D matrix where rows and columns denote vertices. Each entry in the matrix represents the weight of the edge between those vertices. 

Below is the implementation of Graph Data Structure represented using Adjacency Matrix:

Adjacency List Representation of Graph:

This graph is represented as a collection of linked lists. There is an array of pointer which points to the edges connected to that vertex. 

Below is the implementation of Graph Data Structure represented using Adjacency List:

Comparison between Adjacency Matrix and Adjacency List

When the graph contains a large number of edges then it is good to store it as a matrix because only some entries in the matrix will be empty. An algorithm such as Prim’s and Dijkstra adjacency matrix is used to have less complexity.

Basic Operations on Graph Data Structure:

Below are the basic operations on the graph:

• Add and Remove vertex in Adjacency List representation of Graph
• Add and Remove vertex in Adjacency Matrix representation of Graph
• Add and Remove Edge in Adjacency List representation of a Graph
• Add and Remove Edge in Adjacency Matrix representation of a Graph
• Searching in Graph Data Structure- Search an entity in the graph.
• Traversal of Graph Data Structure- Traversing all the nodes in the graph.

Difference between Tree and Graph:

Tree is a restricted type of Graph Data Structure, just with some more rules. Every tree will always be a graph but not all graphs will be trees. Linked List , Trees , and Heaps all are special cases of graphs. 

Real-Life Applications of Graph Data Structure:

Graph Data Structure has numerous real-life applications across various fields. Some of them are listed below:

• If we recall all the previous data structures that we have studied like array, linked list, tree, etc. All these had some restrictions on structure (mostly linear and tree hierarchical which means no loops). Graph allows random connections between nodes which is useful in many real world problems where do have restrictions of previous data structures.
• Used heavily in social networks. Everyone on the network is a vertex (or node) of the graph and if connected, then there is an edge. Now imagine all the features that you see, mutual friends, people that follow you, etc can seen as graph problems.
• Used to represent the topology of computer networks, such as the connections between routers and switches.
• Used to represent the connections between different places in a transportation network, such as roads and airports.
• Neural Networks: Vertices represent neurons and edges represent the synapses between them. Neural networks are used to understand how our brain works and how connections change when we learn. The human brain has about 10^11 neurons and close to 10^15 synapses.
• Compilers: Graph Data Structure is used extensively in compilers. They can be used for type inference, for so-called data flow analysis, register allocation, and many other purposes. They are also used in specialized compilers, such as query optimization in database languages.
• Robot planning: Vertices represent states the robot can be in and the edges the possible transitions between the states. Such graph plans are used, for example, in planning paths for autonomous vehicles.
• Dependencies in a software project (or any other type of project) can be seen as graph and generating a sequence to solve all tasks before dependents is a standard graph topological sorting algorithm.
• For optimizing the cost of connecting all locations of a network. For example, minimizing wire length in a wired network to make sure all devices are connected is a standard Graph problem called Minimum Spanning Tree.

Advantages of Graph Data Structure:

• Graph Data Structure used to represent a wide range of relationships as we do not have any restrictions like previous data structures (Tree cannot have loops and have to be hierarchical. Arrays, Linked List, etc are linear)
• They can be used to model and solve a wide range of problems, including pathfinding, data clustering, network analysis, and machine learning.
• Any real world problem where we certain set of items and relations between them can be easily modeled as a graph and a lot of standard graph algorithms like BFS, DFS, Spanning Tree, Shortest Path, Topological Sorting and Strongly Connected
• Graph Data Structure can be used to represent complex data structures in a simple and intuitive way, making them easier to understand and analyze.

Disadvantages of Graph Data Structure:

• Graph Data Structure can be complex and difficult to understand, especially for people who are not familiar with graph theory or related algorithms.
• Creating and manipulating graphs can be computationally expensive, especially for very large or complex graphs.
• Graph algorithms can be difficult to design and implement correctly, and can be prone to bugs and errors.
• Graph Data Structure can be difficult to visualize and analyze, especially for very large or complex graphs, which can make it challenging to extract meaningful insights from the data.

Frequently Asked Questions(FAQs) on Graph Data Structure:

1. what is a graph.

A graph is a data structure consisting of a set of vertices (nodes) and a set of edges that connect pairs of vertices.

2. What are the different types of Graph Data Structure?

Graph Data Structure can be classified into various types based on properties such as directionality of edges (directed or undirected), presence of cycles (acyclic or cyclic), and whether multiple edges between the same pair of vertices are allowed (simple or multigraph).

3. What are the applications of Graph Data Structure?

Graph Data Structure has numerous applications in various fields, including social networks, transportation networks, computer networks, recommendation systems, biology, chemistry, and more.

4. What is the difference between a directed graph and an undirected graph?

In an undirected graph, edges have no direction, meaning they represent symmetric relationships between vertices. In a directed graph (or digraph), edges have a direction, indicating a one-way relationship between vertices.

5. What is a weighted graph?

A weighted graph is a graph in which each edge is assigned a numerical weight or cost. These weights can represent distances, costs, or any other quantitative measure associated with the edges.

6. What is the degree of a vertex in a graph?

The degree of a vertex in a graph is the number of edges incident to that vertex. In a directed graph, the indegree of a vertex is the number of incoming edges, and the outdegree is the number of outgoing edges.

7. What is a path in a graph?

A path in a graph is a sequence of vertices connected by edges. The length of a path is the number of edges it contains.

8. What is a cycle in a graph?

A cycle in a graph is a path that starts and ends at the same vertex, traversing a sequence of distinct vertices and edges in between.

9. What are spanning trees and minimum spanning trees?

A spanning tree of a graph is a subgraph that is a tree and includes all the vertices of the original graph. A minimum spanning tree (MST) is a spanning tree with the minimum possible sum of edge weights.

10. What algorithms are commonly used to traverse or search Graph Data Structure?

Common graph traversal algorithms include depth-first search (DFS) and breadth-first search (BFS). These algorithms are used to explore or visit all vertices in a graph, typically starting from a specified vertex. Other algorithms, such as Dijkstra’s algorithm and Bellman-Ford algorithm, are used for shortest path finding.

More Resources of Graph:

• Recent Articles on Graph
• Practice problems on Graph
• Algorithms on Graphs

Please Login to comment...

Similar reads.

• Data Structures
• Top Android Apps for 2024
• Top Cell Phone Signal Boosters in 2024
• Best Travel Apps (Paid & Free) in 2024
• The Best Smart Home Devices for 2024
• 15 Most Important Aptitude Topics For Placements [2024]

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Versatile Multi-stage Graph Neural Network for Circuit Representation

Part of Advances in Neural Information Processing Systems 35 (NeurIPS 2022) Main Conference Track

Shuwen Yang, Zhihao Yang, Dong Li, Yingxueff Zhang, Zhanguang Zhang, Guojie Song, Jianye Hao

Due to the rapid growth in the scale of circuits and the desire for knowledge transfer from old designs to new ones, deep learning technologies have been widely exploited in Electronic Design Automation (EDA) to assist circuit design. In chip design cycles, we might encounter heterogeneous and diverse information sources, including the two most informative ones: the netlist and the design layout. However, handling each information source independently is sub-optimal. In this paper, we propose a novel way to integrate the multiple information sources under a unified heterogeneous graph named Circuit Graph, where topological and geometrical information is well integrated. Then, we propose Circuit GNN to fully utilize the features of vertices, edges as well as heterogeneous information during the message passing process. It is the first attempt to design a versatile circuit representation that is compatible across multiple EDA tasks and stages. Experiments on the two most representative prediction tasks in EDA show that our solution reaches state-of-the-art performance in both logic synthesis and global placement chip design stages. Besides, it achieves a 10x speed-up on congestion prediction compared to the state-of-the-art model.

Name Change Policy

Requests for name changes in the electronic proceedings will be accepted with no questions asked. However name changes may cause bibliographic tracking issues. Authors are asked to consider this carefully and discuss it with their co-authors prior to requesting a name change in the electronic proceedings.

Use the "Report an Issue" link to request a name change.

{{errorText}}

Visit www.aminer.cn directly for more AI services.

Go to AMiner

error code: {{errorCode}}

Logging off

Search for peer-reviewed journals with full access.

Discover the SciOpen Platform and Achieve Your Research Goals with Ease.

Multi-Relational Graph Representation Learning for Financial Statement Fraud Detection

Financial statement fraud refers to malicious manipulations of financial data in listed companies’ annual statements. Traditional machine learning approaches focus on individual companies, overlooking the interactive relationships among companies that are crucial for identifying fraud patterns. Moreover, fraud detection is a typical imbalanced binary classification task with normal samples outnumbering fraud ones. In this paper, we propose a multi-relational graph convolutional network, named FraudGCN, for detecting financial statement fraud. A multi-relational graph is constructed to integrate industrial, supply chain, and accounting-sharing relationships, effectively encapsulating the multidimensional and complex interactions among companies. We then develop a multi-relational graph convolutional network to aggregate information within each relationship and employ an attention mechanism to fuse information across multiple relationships. The attention mechanism enables the model to distinguish the importance of different relationships, thereby aggregating more useful information from key relationships. To alleviate the class imbalance problem, we present a diffusion-based under-sampling strategy that strategically selects key nodes globally for model training. We also employ focal loss to assign greater weights to harder-to-classify minority samples. We build a real-world dataset from the annual financial statement of listed companies in China. The experimental results show that FraudGCN achieves an improvement of 3.15% in Macro-recall, 3.36% in Macro-F1, and 3.86% in GMean compared to the second-best method. The dataset and codes are publicly available at: https://github.com/XNetLab/MRG-for-Finance.

No abstract is available for this article. Click the button above to view the PDF directly.

P. Ravisankar, V. Ravi, G. R. Rao, and I. Bose, Detection of financial statement fraud and feature selection using data mining techniques, Decis. Support Syst. , vol. 50, no. 2, pp. 491–500, 2011.

S. Barman, U. Pal, A. Sarfaraj, B. Biswas, A. Mahata, and P. Mandal, A complete literature review on financial fraud detection applying data mining techniques, Int. J. Trust Manage. Comput. Commun. , vol. 3, no. 4, pp. 336–359, 2016.

G. Niu, L. Yu, G. Z. Fan, and D. Zhang, Corporate fraud, risk avoidance, and housing investment in China, Emerg. Mark. Rev. , vol. 39, pp. 18–33, 2019.

M. Jusup, P. Holme, K. Kanazawa, M. Takayasu, I. Romić, Z. Wang, S. Geček, T. Lipić, B. Podobnik, L. Wang, et al., Social physics, Phys. Rep. , vol. 948, pp. 1–148, 2022.

L. G. A. Alves, H. Y. D. Sigaki, M. Perc, and H. V. Ribeiro, Collective dynamics of stock market efficiency, Sci. Rep. , vol. 10, no. 1, p. 21992, 2020.

D. Fister, M. Perc, and T. Jagrič, Two robust long short-term memory frameworks for trading stocks, Appl. Intell. , vol. 51, no. 10, pp. 7177–7195, 2021.

A. A. B. Pessa, M. Perc, and H. V. Ribeiro, Age and market capitalization drive large price variations of cryptocurrencies, Sci. Rep. , vol. 13, no. 1, p. 3351, 2023.

B. Baesens, S. Höppner, and T. Verdonck, Data engineering for fraud detection, Decis. Support Syst. , vol. 150, p. 113492, 2021.

K. G. Al-Hashedi and P. Magalingam, Financial fraud detection applying data mining techniques: A comprehensive review from 2009 to 2019, Comput. Sci. Rev. , vol. 40, p. 100402, 2021.

P. S. Stanimirovic, Fraud detection in publicly traded us firms using beetle antennae search: A machine learning approach, Expert Systems with Applications , vol. 191, p. 116148, 2022.

P. M. Dechow, W. Ge, C. R. Larson, and R. G. Sloan, Predicting material accounting misstatements, Contemp. Account. Res. , vol. 28, no. 1, pp. 17–82, 2011.

P. Craja, A. Kim, and S. Lessmann, Deep learning for detecting financial statement fraud, Decis. Support Syst. , vol. 139, p. 113421, 2020.

Z. Sabir, H. A. Wahab, S. Javeed, and H. M. Baskonus, An efficient stochastic numerical computing framework for the nonlinear higher order singular models, Fractal Fract. , vol. 5, no. 4, p. 176, 2021.

Z. Sabir, K. Nisar, M. A. Z. Raja, A. A. B. A. Ibrahim, J. J. P. C. Rodrigues, K. S. Al-Basyouni, S. R. Mahmoud, and D. B. Rawat, Heuristic computational design of morlet wavelet for solving the higher order singular nonlinear differential equations, Alex. Eng. J. , vol. 60, no. 6, pp. 5935–5947, 2021.

S. C. L. Koh, M. Demirbag, E. Bayraktar, E. Tatoglu, and S. Zaim, The impact of supply chain management practices on performance of SMEs, Ind. Manage. Data Syst. , vol. 107, no. 1, pp. 103–124, 2007.

M. Abed and B. Fernando, E-commerce fraud detection based on machine learning techniques: Systematic literature review, Big Data Mining and Analytics , vol. 7, no.2, pp. 419−444, 2024.

J. Perols, Financial statement fraud detection: An analysis of statistical and machine learning algorithms, Audit. : A J. Pract. Theory , vol. 30, no. 2, pp. 19–50, 2011.

W. H. Beaver, Financial ratios as predictors of failure, J. Account. Res. vol. 4, no. 1, pp. 71–111, 1966.

M. Cecchini, H. Aytug, G. J. Koehler, and P. Pathak, Detecting management fraud in public companies, Manage. Sci. , vol. 56, no. 7, pp. 1146–1160, 2010.

S. Kotsiantis, E. Koumanakos, D. Tzelepis, V. Tampakas, Forecasting fraudulent financial statements using data mining, Int. J. Comput. Intell. , vol. 3, no. 2, pp. 104–110, 2006.

H. C. Koh and C. K. Low, Going concern prediction using data mining techniques, Manag. Audit. J. , vol. 19, no. 3, pp. 462–476, 2004.

C. Liu, Y. Chan, S. H. A. Kazmi, and H. Fu, Financial fraud detection model: Based on random forest, Int. J. Econ. Finance , vol. 7, no. 7, pp. 178–188, 2015.

M. Cecchini, H. Aytug, G. J. Koehler, and P. Pathak, Making words work: Using financial text as a predictor of financial events, Decis. Support Syst. , vol. 50, no. 1, pp. 164–175, 2010.

Y. Y. Chen, Forecasting financial distress of listed companies with textual content of the information disclosure: A study based MD&A in Chinese annual reports, (in Chinese), Chin. J. Manage. Sci. , vol. 27, no. 7, pp. 23–34, 2019.

A. Dyck, A. Morse, and L. Zingales, Who blows the whistle on corporate fraud? J. Finance , vol. 65, no. 6, pp. 2213–2253, 2010.

P. Hajek and R. Henriques, Mining corporate annual reports for intelligent detection of financial statement fraud—A comparative study of machine learning methods, Knowl. -Based Syst. , vol. 128, pp. 139–152, 2017.

J. L. Hobson, W. J. Mayew, and M. Venkatachalam, Analyzing speech to detect financial misreporting, J. Account. Res. , vol. 50, no. 2, pp. 349–392, 2012.

W. Dong, S. Liao, and Z. Zhang, Leveraging financial social media data for corporate fraud detection, J. Manage. Inf. Syst. , vol. 35, no. 2, pp. 461–487, 2018.

G. Ozdagoglu, A. Ozdagoglu, Y. Gumus, and G. Kurt Gumus, The application of data mining techniques in manipulated financial statement classification: The case of turkey, J. AI Data Mining. , vol. 5, no. 1, pp. 67–77, 2017.

X. B. Tang, G. C. Liu, J. Yang, and W. Wei, Knowledge-based financial statement fraud detection system: Based on an ontology and a decision tree, Knowl. Org. , vol. 45, no. 3, pp. 205–219, 2018.

Y. Bao, B. Ke, B. Li, Y. J. Yu, and J. Zhang, Detecting accounting fraud in publicly traded U. S. firms using a machine learning approach, J. Account. Res. , vol. 58, no. 1, pp. 199–235, 2020.

X. Wu and S. Du, An analysis on financial statement fraud detection for Chinese listed companies using deep learning, IEEE Access , vol. 10, pp. 22516–22532, 2022.

Z. Sabir, M. A. Z. Raja, A. S. Alnahdi, M. B. Jeelani, and M. A. Abdelkawy, Numerical investigations of the nonlinear smoke model using the Gudermannian neural networks, Math. Biosci. Eng , vol. 19, no. 1, pp. 351–370, 2022.

Z. Sabir, M. A. Z. Raja, J. L. G. Guirao, and T. Saeed, Meyer wavelet neural networks to solve a novel design of fractional order pantograph lane-emden differential model, Chaos Solitons Fractals , vol. 152, p. 111404, 2021.

Z. Sabir, M. A. Z. Raja, H. A. Wahab, M. Shoaib, and J. F. G. Aguilar, Integrated neuro-evolution heuristic with sequential quadratic programming for second-order prediction differential models, Numer. Methods Part. Differ. Equations , vol. 40, no. 1, p. e22692, 2024.

K. Nisar, Z. Sabir, M. A. Z. Raja, A. A. A. Ibrahim, F. Erdogan, M. R. Haque, J. J. P. C. Rodrigues, and D. B. Rawat, Design of morlet wavelet neural network for solving a class of singular pantograph nonlinear differential models, IEEE Access , vol. 9, pp. 77845–77862, 2021.

Z. Sabir, Neuron analysis through the swarming procedures for the singular two-point boundary value problems arising in the theory of thermal explosion, Eur. Phys. J. Plus , vol. 137, no. 5, p. 638, 2022.

Z. Sabir, T. Botmart, M. A. Z. Raja, R. Sadat, M. R. Ali, A. A. Alsulami, and A. Alghamdi, Artificial neural network scheme to solve the nonlinear influenza disease model, Biomed. Signal Process. Control , vol. 75, p. 103594, 2022.

J. Zhou, G. Cui, S. Hu, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun, Graph neural networks: A review of methods and applications, AI Open , vol. 1, pp. 57–81, 2020.

X. Mao, H. Sun, X. Zhu, and J. Li, Financial fraud detection using the related-party transaction knowledge graph, Procedia Comput. Sci. , vol. 199, pp. 733–740, 2022.

L. Page, S. Brin, R. Motwani, and T. Winograd, The PageRank citation ranking: bringing order to the web, Stanford Digital Libraries Working Paper .

P. Christoffersen and K. Jacobs, The importance of the loss function in option valuation, J. Financ. Econ. , vol. 72, no. 2, pp. 291–318, 2004.

U. Ruby and V. Yendapalli, Binary cross entropy with deep learning technique for image classification, Int. J. Adv. Trends Comput. Sci. Eng , vol. 9, no. 4, pp. 5393–5397, 2020.

F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, et al., Scikit-learn: Machine learning in python, J. Mach. Learn. Res. , vol. 12, pp. 2825–2830, 2011.

W. Caesarendra, A. Widodo, and B. S. Yang, Application of relevance vector machine and logistic regression for machine degradation assessment, Mech. Syst. Signal Process. , vol. 24, no. 4, pp. 1161–1171, 2010.

W. Tong, H. Hong, H. Fang, Q. Xie, and R. Perkins, Decision forest: Combining the predictions of multiple independent decision tree models, J. Chem. Inf. Comput. Sci. , vol. 43, no. 2, pp. 525–531, 2003.

L. Y. Hu, M. W. Huang, S. W. Ke, and C. F. Tsai, The distance function effect on k-nearest neighbor classification for medical datasets, SpringerPlus , vol. 5, no. 1, p. 1304, 2016.

X. Zhao, Z. Ma, and M. Yin, Using support vector machine and evolutionary profiles to predict antifreeze protein sequences, Int. J. Mol. Sci. , vol. 13, no. 2, pp. 2196–2207, 2012.

J. H. Friedman, Greedy function approximation: A gradient boosting machine, Ann. Statist. , vol. 29, no. 5, pp. 1189–1232, 2001.

M. Sokolova and G. Lapalme, A systematic analysis of performance measures for classification tasks, Inf. Process. Manage. , vol. 45, no. 4, pp. 427–437, 2009.

L. van der Maaten and G. Hinton, Visualizing data using t-SNE, J. Mach. Learn. Res. , vol. 9, no. 86, pp. 2579–2605, 2008.

Web of Science

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License ( http://creativecommons.org/licenses/by/4.0/ ).

京ICP备 10035462号-42

• Open access
• Published: 02 September 2024

Med-MGF: multi-level graph-based framework for handling medical data imbalance and representation

• Tuong Minh Nguyen 1 ,
• Kim Leng Poh 1 ,
• Shu-Ling Chong 2 , 3 &
• Jan Hau Lee 3 , 4  

BMC Medical Informatics and Decision Making volume  24 , Article number:  242 ( 2024 ) Cite this article

Metrics details

Modeling patient data, particularly electronic health records (EHR), is one of the major focuses of machine learning studies in healthcare, as these records provide clinicians with valuable information that can potentially assist them in disease diagnosis and decision-making.

In this study, we present a multi-level graph-based framework called MedMGF, which models both patient medical profiles extracted from EHR data and their relationship network of health profiles in a single architecture. The medical profiles consist of several layers of data embedding derived from interval records obtained during hospitalization, and the patient-patient network is created by measuring the similarities between these profiles. We also propose a modification to the Focal Loss (FL) function to improve classification performance in imbalanced datasets without the need to imputate the data. MedMGF’s performance was evaluated against several Graphical Convolutional Network (GCN) baseline models implemented with Binary Cross Entropy (BCE), FL, class balancing parameter \(\alpha\) , and Synthetic Minority Oversampling Technique (SMOTE).

Our proposed framework achieved high classification performance (AUC: 0.8098, ACC: 0.7503, SEN: 0.8750, SPE: 0.7445, NPV: 0.9923, PPV: 0.1367) on an extreme imbalanced pediatric sepsis dataset (n=3,014, imbalance ratio of 0.047). It yielded a classification improvement of 3.81% for AUC, 15% for SEN compared to the baseline GCN+ \(\alpha\) FL (AUC: 0.7717, ACC: 0.8144, SEN: 0.7250, SPE: 0.8185, PPV: 0.1559, NPV: 0.9847), and an improvement of 5.88% in AUC and 22.5% compared to GCN+FL+SMOTE (AUC: 0.7510, ACC: 0.8431, SEN: 0.6500, SPE: 0.8520, PPV: 0.1688, NPV: 0.9814). It also showed a classification improvement of 3.86% for AUC, 15% for SEN compared to the baseline GCN+ \(\alpha\) BCE (AUC: 0.7712, ACC: 0.8133, SEN: 0.7250, SPE: 0.8173, PPV: 0.1551, NPV: 0.9847), and an improvement of 14.33% in AUC and 27.5% in comparison to GCN+BCE+SMOTE (AUC: 0.6665, ACC: 0.7271, SEN: 0.6000, SPE: 0.7329, PPV: 0.0941, NPV: 0.9754).

When compared to all baseline models, MedMGF achieved the highest SEN and AUC results, demonstrating the potential for several healthcare applications.

Peer Review reports

Introduction

Making an accurate medical diagnosis for a patient requires consideration of several aspects of clinical information and evidence. This includes reviewing the patient’s medical history, performing physical examinations, ordering tests, interpreting test results, and consulting with other professionals if necessary. The data collected during this process are mainly stored as tabular Electronic health records (EHR) (e.g., vital signs, laboratory results), high-frequency physiologic waveforms (e.g., electrocardiogram), imaging (e.g., radiograph), or other forms of medical data. Using these data, clinicians are able to monitor the patient’s disease progression and make informed treatment decisions. As it contains a large volume of rich clinical information, EHR can potentially be used to support clinical research as well [ 1 , 2 ]. The use of EHR as a data source for Machine learning (ML) studies has increased significantly over the past few years, and modeling EHR data has been one of the major focuses of ML applications in the healthcare sector [ 3 , 4 ].

The concept of Patient similarity network (PSN) is an emerging research field within the context of precision medicine [ 5 , 6 ]. The diagnosis made using this network is based on the premise that if patients’ medical data are similar in several aspects, then their clinical progress should be similar as well. It is hypothesized that a common disease trajectory resulting in a specific outcome may establish a similarity between patients, thereby making the insight gained using PSN more reliable and robust [ 7 ]. Recent advances in ML techniques have led to the development of a variety methods to construct PSN. The International classification of diseases (ICD) was often utilized to establish connections between patients [ 8 , 9 ]. In some instances, medical inputs are converted into feature vectors and the distance between these vectors will determine the degree of similarity between them [ 7 , 10 ]. Studies usually treat the medical inputs as a flat structure or embed them within several layers of neural networks without preserving their structure or interpretation. The latter often requires a separate training process to create the medical embedding before they are introduced into the PSN for further training, which could result in an increase in training costs.

In this work, we propose Medical Multilevel Graph-based Framework (MedMGF), a framework that is capable of modeling medical data, as well as representing the patient’s individual medical profile and their similarity to other patients within a single architecture. Depending on data availability, the medical profile can be constructed from EHR, physiologic waveforms, imaging data, or a combination thereof. In this study, we demonstrate the feasibility of the framework using EHR data. In contrast to most studies which treat EHR as a flat structure, we preserve its natural hierarchical structure and provide an intuitive way to describe it by incorporating interval data from multiple hospitalizations. A multi-level embedding process allows the medical inputs to pass directly through the PSN, where embedding and PSN are optimized through a single training procedure. We also propose a modification of the Focal Loss (FL, [ 11 ]) function to improve classification performance on imbalanced datasets without having to imputate the data, thus reducing the amount of preprocessing needed. In general, MedMGF encapsulates the following characteristics: (1) generality and modality, (2) multi-purpose, (3) intuitive interpretation, and (4) minimal data requirements.

In this study, our objective is to present the framework architecture and feasibility of MedMGF on an imbalanced pediatric sepsis EHR datasets and evaluate its classification performance against several Graph Convolutional Network (GCN, [ 12 ]) baselines implemented with Binary Cross Entropy (BCE, [ 13 ]), FL, class balancing parameter \(\alpha\) , and Synthetic Minority Over-sampling Technique (SMOTE, [ 14 ]).

Related works

Electronic health record modeling.

The use of ML in modelling EHR has become more prevalent as EHR contains rich clinical information that can potentially assist clinicians in making diagnosis and treatment decisions. Although most studies model the EHR in a flat manner [ 15 , 16 ], exploring its structural aspects may reveal new possibilities for enhancing the model. In particular, Choi et al. developed Multi-layer Representation Learning for Medical concepts (Med2Vec, [ 17 ]), and continue to explore this approach with Graph-based Attention Model (GRAM, [ 18 ]) and Multi-level Medical Embedding (MiME, [ 19 ]). By leveraging the parent-child relationship on the knowledge-based directed graph, GRAM can learn the representation of medical concepts (e.g., ICD codes) with attention mechanisms and predict the next hospital visit’s diagnosis code. Based on GRAM, Li et al. developed Multimodal Diagnosis Prediction model (MDP, [ 20 ]) that allows clinical data to be integrated into the framework. Although clinical data from EHR can be weighed dynamically to highlight the most important features, the data is still processed in a flat manner. With MiME, Choi et al. constructed a hierarchical structure of EHR data based on the relationship between symptoms and treatments, where the hospital visit consists of a number of symptoms, each corresponding to a number of specific treatments. This influential interaction is encapsulated in the patient’s data embedding representation, which is used for prediction purposes. The precision-recall area under the curve (PR-AUC) for heart failure prediction showed a 15% improvement compared to the baseline model. As most EHR datasets lack the connection between symptoms and treatments, MiME may require extensive data preprocessing, and EHR data may need to undergo a rigorous pre-processing procedure before being mapped to MiME. In addition, the current MiME structure may not capture all aspects of EHR data, other than the relationship between symptoms and treatments. In light of these two drawbacks, we propose MedMGF, a framework for modeling EHR data that can capture all aspects of EHR efficiently and effectively with minimal data preprocessing required.

Patient similarity network

There are several approaches to constructing a PSN using ICD codes [ 8 , 9 ]. One of the approaches is to create a bipartite graph to connect patients to their corresponding ICDs in a similar manner to what Lu and Uddin did in 2021. This bipartite graph is then converted into a weighted PSN, in which the weight of the edge is determined by the number of mutual ICD codes between the patients [ 9 ]. In this approach, the number of mutual ICD codes used to connect patients is highly dependent upon cohort and ICD code selection. In Rouge et al.’s study, an inverse document frequency measured vector of 674 ICD10 codes was constructed for each patient. A cosine similarity between these vectors was calculated for all possible pairs of patients. The PSN was then constructed using a pre-defined threshold on the calculated distances [ 8 ]. As the number of patients increases, it becomes more difficult to process the large ICD matrix computationally. In other cases, the medical input is mapped into feature vectors, and distance metrics (e.g. Euclidean, Cosine, Manhattan) are applied to determine the degree of similarity [ 8 , 10 ]. In the work of Navaz et al., two similarity matrices were calculated separately for static data (e.g. age) and dynamic data (e.g. vital signs). These matrixes were then fused together to construct the PSN [ 7 ].

Focal loss function

FL function was first introduced by Lin et al. in 2018 [ 11 ]. On the training data \(\mathcal {D}=\{(\textbf{x}_i,y_i)\}^N_i\) independently drawn from an i.i.d probability distribution, the FL for a binary classification problem is defined as follows:

where p is the predicted probability and \(\gamma \ge 0\) is a user-defined hyperparameter to control the rate at which easy samples are down-weighted. It can be observed that FL reduces to the Cross Entropy (CE) when \(\gamma = 0\) . FL introduces a modulating factor \((1-p_t)^\gamma\) to the CE to dynamically adjust the loss based on the difficulty of each sample. This factor is higher for misclassified samples and lower for well-classified samples. Thus, FL reduces the impact of the dominant class by focusing on difficult samples. Researchers typically perform cross-validation to find the optimal value of gamma [ 11 , 21 ]. In a strategic policy proposed by Mukhoti et al., a higher value of \(\gamma\) would be allocated to predicted probabilities, which is less than a pre-calculated threshold and a lower value of \(\gamma\) for probabilities greater than the threshold [ 22 ]. The results of their work showed that the dynamic value of \(\gamma\) could improve FL calibration. In another work, Ghosh et al. proposed to dynamically adjusted \(\gamma\) based on its value from the previous steps [ 23 ]. Either way, the classification performance is strongly influenced by and dependent on the value of \(\gamma\) . Considering this dependence, we propose a modification that allows us to dynamically adjust the modulating factor in a similar manner without relying on the hyperparameter \(\gamma\) .

The framework consists of three main components: the patient’s medical profile, which represents the health data extracted from the EHR data, the patient-patient network, which represents the similarity among the patients, based on their profiles, and the modification of FL function. An individual’s medical profile is constructed based on a hierarchical representation that embeds several layers of information derived from interval data collected during hospitalizations and medical modules. In this study, we present the medical representation for EHR data. The overall framework is illustrated in Fig. 1 . The notation for patient’s medical profile and patient-patient network are listed in Tables 1 and  2 .

The MedMGF framework consists of several layers of medical data embedding

Patient’s medical profile

Suppose that an individual’s medical profile for a specific disease contains health data from a sequence of hospitalizations \(\left( \mathcal {V}^{(1)},\mathcal {V}^{(2)},...,\mathcal {V}^{(i)},...,\mathcal {V}^{(T)}\right)\) , whereat each hospitalization \(\mathcal {V}^{(i)}\) , a sequence of medical data \(\left( \mathcal {D}^{(1)},\mathcal {D}^{(2)},...,\mathcal {D}^{(j)},...,\mathcal {D}^{(t)}\right)\) is entered at time intervals \(\left( \Delta _1,\Delta _2,...,\Delta _j,...,\Delta _t\right)\) , with \(\Delta _j\) being the time interval between \(\mathcal {D}^{(j)}\) and \(\mathcal {D}^{(j-1)}\) . Medical data \(\mathcal {D}^{(j)}\) collected at interval j -th includes medical module from EHR data \(\mathcal {S}_{E}^{(j)}\) , imaging data \(\mathcal {S}_{I}^{(j)}\) , signal data \(\mathcal {S}_{S}^{(j)}\) , or a combination thereof, then \(\mathcal {D}^{(j)} = \oplus \left( \mathcal {S}_{E}^{(j)},\mathcal {S}_{I}^{(j)},\mathcal {S}_{S}^{(j)},...\right)\) , where \(\oplus (.)\) represents the CONCAT data aggregation function. Let \(\textbf{d}^{(j)}\) be the vector representation of \(\mathcal {D}^{(j)}\) at j -th interval, \(\textbf{v}^{(i)}\) be a vector representation of i -th hospitalization \(\mathcal {V}^{(i)}\) , and \(\textbf{s}_{E}^{(j)},\textbf{s}_{I}^{(j)},\textbf{s}_{S}^{(j)}\) be the vector representation of \(\mathcal {S}_{E}^{(j)},\mathcal {S}_{I}^{(j)},\mathcal {S}_{S}^{(j)}\) , then \(\textbf{d}^{(j)} = \oplus \left( \textbf{s}_{E}^{(j)},\textbf{s}_{I}^{(j)},\textbf{s}_{S}^{(j)},...\right)\) and \(\textbf{v}^{(i)} = \oplus \left( \textbf{d}^{(1)}, \textbf{d}^{(2)},...,\textbf{d}^{(j)},...,\textbf{d}^{(t)}\right) \in \mathbb {R}^{t \times z}\) , where z represents the number of the medical modules. We define \(\textbf{h}\) to be the vector presentation of a patient’s medical profile, then \(\textbf{h}= \oplus \left( \textbf{v}^{(1)}, \textbf{v}^{(2)},..., \textbf{v}^{(i)},...,\textbf{v}^{(T)} \right)\) .

The interval sequence \(\left( \Delta _1,\Delta _2...,\Delta _t\right)\) represents the irregular periodicity of the hospital data, where \(\Delta _i\) can vary to match the requirement of the desired analysis. For this study, we fix \(\Delta _1 = \Delta _2=...= \Delta _t = \Delta\) so that the medical data will be extracted at a fixed interval \(\Delta\) . Different variables are collected at different intervals, resulting in three possible scenarios: no value is recorded, one value is recorded, or multiple values are recorded. We extract the variables value of an interval as follows: if no data are available for interval j -th, the value from the previous interval will be carried forward. If more than one value is recorded in the interval, the worst value will be taken (Fig. 2 ).

Data extraction rule at an interval: when no value is available during the interval, the value from previous interval is carried forward. A worst value is selected if more than one value is available in the interval

Patient-patient medical profile network

The patient’s medical profile network is defined as a graphical network \(\mathcal {G} = \left( V,E,X,A\right)\) with \(|V| = N\) nodes and | E | edges, where nodes represent patients and the edge weights represent the degree of similarity between them. The node feature matrix \(X =(\textbf{x}_1, \textbf{x}_2, \textbf{x}_3,...,\textbf{x}_n) \in \mathbb {R}^{N \times T}\) contains the feature vector of all nodes. A single row \(\textbf{x}_i\) from the node matrix X is a representation of a patient’s medical profile from T hospitalizations that has been described in “ Patient’s medical profile ” section. Hence, \(\textbf{x}_i = \textbf{h}_i = \left\{ \textbf{v}^{(1)}, \textbf{v}^{(2)},..., \textbf{v}^{(i)},...,\textbf{v}^{(T)} \right\}\) . In order to determine a the similarity between patients, we measure the similarity between their medical profiles. Since the medical profile is represented as a data vector, we can measure the similarity between patient’s medical profile by calculating the Euclidean distance between them. Let \(u,v \in V\) be the two nodes representing patient u and v on \(\mathcal {G}\) , the similarity distance d ( u ,  v ) is defined as follows:

Using Eq. 3 , an Euclidean distance matrix can be constructed for \(\mathcal {G}\) . This distance matrix allows us to construct a patient-patient medical profile network \(\mathcal {G}\) . If we assume that no two patient’s profiles are absolutely identical, then \(\mathcal {G}\) will be a complete network. Patients with similar profiles will stay close to each other, forming several clusters in the network representation. As connections between very different profiles may produce noise data for classification, we define a similarity threshold \(\xi\) to control the number of connections on \(\mathcal {G}\) .

The connection between nodes u ,  v is represented by \((u,v)\in E\) , and \((u,v) = \mathbbm{1}\{d(u,v) \le \xi : u,v \in V\}\) . The adjacency matrix is then expressed as \(A \in \mathbb {R}^{N\times N}\) , \(A_{uv} = \mathbbm{1}\{(u,v)=1: (u,v)\in E, u,v \in V\}\) . The construction of patient’s medical profile network consists of the following steps:

Calculate the Euclidean similarity matrix using the node feature matrix X and Eq. 3 .

Setting a threshold \(\xi\) for the similarity matrix .

Using the thresholded similarity matrix, construct the adjacency matrix A and network \(\mathcal [G]\) .

Tree-structure representation of EHR

EHRs are often formatted similarly to relational databases, where variables are categorized by their interpretation into tables, such as demographic information, vital signs, and laboratory results. By leveraging this relationship, the EHR can be easily represented as a tree structure, where a table i is mapped with an object denoted as \(\textbf{o}_i^{(t)}\) and variable j recorded under the table is denoted as \(\textbf{o}_{ij}^{(t)}\) (Fig. 3 ). In this section, the t -th interval will be dropped to simplify the notation. i and j will be used as the notation for the nodes representing the corresponding objects. The tree-based representation of EHR data is defined as a \(\mathcal {T} = (\mathcal {P},\mathcal {C},\mathcal {A})\) , where \(\mathcal {P}\) is a set of parent nodes and \(\mathcal {C}\) is a set of child nodes. Let \(i \in \mathcal {P}\) and \(j \in \mathcal {C}\) then the connection between parent and child is represented by \((i,j)\in \mathcal {A}\) . The adjacency matrix is expressed as \(\mathcal {A} \in \mathbb {R}^{|\mathcal {P}|\times |\mathcal {C}|}\) , \(\mathcal {A}_{ij} = 1\) if there is a connection between them or \(\mathcal {A}_{ij} = 0\) otherwise. An empty root node \(R_{\mathcal {T}}\) is added to \(\mathcal {P}\) to receive the final data embedding and its connection to the existing parent nodes are added to \(\mathcal {A}\) . The data embedding in the tree structure is carried from child node to parent node recursively from the bottom to the root node. The notation summary is listed in Table 3 . The data embedding at any parent node is as follows:

In Eq. 4 , the data of child nodes \(\textbf{o}_{ij}\) are transformed by multiplying with weight matrix \(\textbf{W}_i \in \mathbb {R}^{j}\) , which are then summed together to obtain the embedding of the object group \(\textbf{o}_i\) . At the root node, the data is aggregated with a CONCAT function. Hence, the data embedding vector at the root node \(\textbf{s}_{E} \in \mathbb {R}^{|\mathcal {C(R_\mathcal {T})}|}\) will have the dimension of the number of its child nodes (Eq. 5 ) .

Tree-structure representation of the EHR data

Proposed modification of loss function

Given the training data \(D = \{\textbf{x}_i,y_i\}^N_{i=1}\) , where \(\textbf{x}_i \in \mathbb {R}^d\) is the feature vector of d dimensions and \(y_i \in \{0,1\}\) is the label of the sample i -th. \(\textbf{x}_i\) is extracted from EHR data and is used to construct the patient’s medical profile and patient-patient network as described in the previous sections. Let \(p_t\) be the predicted probability of a patient at node i in the positive class, \(\alpha _t\) is a balancing parameter for imbalanced class, and \(\gamma\) is a user-defined hyperparameter, we propose a modification of the FL function for binary classification as follows:

We propose to use \((1- e^{p_t})^{-1}\) instead of the original factor \((1-p_t)^{\gamma }\) to control the sample weight. Figure 4 shows the weight distribution the modulating term assign to different predicted probability. The proposed modulating factor imposes a more severe penalty for a predicted probability that is further away from the actual probability as compared to the original modulating factor. In this way, it strongly draws the attention of the loss function during the learning process to the wrongly predicted sample, emphasizing the punishment for predicted probabilities that are close to zero. The advantage of this approach over the original FL is that the sample weight can be dynamically adjusted without being dependent on \(\gamma\) , thereby eliminating the need to tune a hyperparameter. A large penalty assigned to a sample that is greatly mispredicted is the driving force behind an improved classification (Fig. 4 ).

The visualization of the sample weight assigned to sample in the original FL and the proposed modification of FL function

Multi-level data embedding & model learning

The data is embedded in a bottom-up manner, folding several layers of the information: medical modules embedding, interval data embedding, and hospitalization embedding. A patient’s medical profile is encoded through the following embedding sequence:

In Eqs. 7 , 8 , and 9 , \(\oplus (.)\) represents a CONCAT aggregation function. The embedding \(\textbf{h}\) is then used to construct the patient-patient network \(\mathcal {G}\) described in “ Patient-patient medical profile network ” section. Let n be a node on \(\mathcal {G}\) and \(\mathcal {N}(n)\) be the neighbors of n on the network, then the final embedding of node n on \(\mathcal {G}\) is encoded as follows:

where \(\textbf{W}\) is a trainable weight matrix to transform the embedding of the neighbor nodes, \(\sigma\) is a softmax activation function. The learning loss is measured by the proposed loss function as described in “ Proposed modification of loss function ” section. The framework is trained and validated in a transductive manner. The training algorithm is shown in Algorithm 1.

Algorithm 1 Psuedo code of the framework training

Dataset and data processing

This study was conducted using the public dataset Pediatric intensive care dataset (PICD), version 1.1.0, which is available in the PhysioNet repository [ 24 ]. The dataset consists of patients aged 0-18 years admitted to the Intensive care units (ICUs) at the Children’s Hospital of Zhejiang University School of Medicine, Zhejiang, China, from 2010-2019. Our previous work, published in 2023, described the method of selecting cohort samples and extracting data [ 25 ]. We follow the same procedure for collecting data and defining sepsis in this study. However, in the current study, only continuous variables were used, and raw demographic, vital sign, and laboratory data were used instead of category-coded data. This study was approved by the National University of Singapore’s Institutional Review Board (NUS-IRB-2024-396).

Evaluation metrics

The evaluation task is to predict the sepsis outcome of the patients in the test set. As it is a binary classification task, we used Accuracy (ACC), Sensitivity (SEN), Specificity (SPE), Negative predictive value (NPV), Positive predictive value (PPV), and Area under the receiver operating characteristic curve (AUC) to evaluate the model performance.

AUC was measured by comparing the true positive rate against the false positive rate. A high AUC indicates the model ability to distinguish the classes in binary classification. The rest of the metrics are derived from the confusion matrix (Table 4 ). SEN, SPE is the proportion of TP among all positives and TN among all negative while PPV, NPV measures the TP and TN among predicted positives and predicted negatives.

Study design

The data was masked in 70% for training and 30% for testing. We trained the MedMGF on training data and reported the model performance on the masked testing data (Fig. 5 ). The evaluation aimed: (1) to validate the overall performance of the framework compared to the baseline models, (2) to compare its effectiveness against the oversampling method, and (3) to verify that the proposed loss function is comparable to existing loss functions. In the first evaluation, we used three sets of baseline models, including Logistic Regression (LR), GCN implemented with BCE, FL, and balancing parameter \(\alpha\) . In the second evaluation, we used GCN+BCE and GCN+FL+SMOTE as the baseline models. As SMOTE is the most common oversampling technique for imbalance data, it was selected for this study. In the third evaluations, we implemented our proposed framework using BCE, FL, with balancing parameter \(\alpha\) as the baseline models. Finally, we used t-distributed stochastic neighbor embedding (t-SNE) plot to visualize the data embedding produced by the MedMGF+ e FL and the best two baseline models (GCN+ \(\alpha\) FL and GCN+ \(\alpha\) BCE) to demonstrate the learning process. The performance of all models was summarized in Table 5 . A summary of the proposed MedMGF and the previous studies (MiME, GRAM, and MDP) was also provided in Table 6 to highlight the differences of our approach.

The training and validation workflow of MedMGF

Models were fine-tuned to perform optimally. \(\gamma\) was selected in the manner that would optimize the model performance and the balancing parameter was set at the imbalance ratio of the dataset \(\alpha _+ = 0.047\) . All models except LR models were trained with Adam optimizer, 10,000 maximum epochs, a learning rate of 0.01. The training was implemented with an early-stopping mechanism, such that the training would be stopped when the validation loss did not decrease after 10 epochs, otherwise the results would be reported at the conclusion of the training process. BCE with logit loss was set up with a mean reduction. The data split in 70% for training and 30% for testing using the sklearn library. The SMOTE oversampling algorithm was implemented using the imblearn library. The t-SNE plot was produced by sklearn library. The framework was implemented in Spyder IDE (MIT, version 5.5.0, Python version 3.9.14).

Statistical methods

We calculated medians [interquartile ranges (IQRs)] and absolute counts (percentage) for continuous and categorical variables, respectively. Differences between the sepsis and non-sepsis cohort were assessed with Mann-Whitney U on continuous and Pearson’s Chi-squared tests on categorical variables. All statistical analyses were performed using Microsoft Excel (version 16.55, Microsoft, USA) with a statistical significance taken as p < 0.05.

Demographic and baseline clinical characteristics of patients

The cohort contains 3,014 admissions with a median age of 1.13 (0.15-4.30) years old and 1,698 (56.3%) males. The number of sepsis-positive cases is 134 (4.4%), which results in an imbalance ratio of 0.047 between classes. A total of three demographic variables (age, length of stay in the intensive care unit, length of stay in the hospital), five vital signs (temperature, heart rate, respiratory rate, diastolic and systolic blood pressure), and 15 laboratory variables are included in the study (Appendix A). An overview of cohort demographics and clinical outcomes can be referred to [ 25 ].

Model performance comparison against baseline model

On PICD (imbalance ratio of 0.047), LR produced predictions overwhelmingly in favor of the dominant class, resulting in a low SEN (0.0256), high ACC (0.9546), SPE (0.9965), and NPV (0.9578). With LR+SMOTE, the classification improved significantly in AUC and SEN (AUC: 0.7740, SEN: 0.7179). Comparing to these baseline models, MedMGF+ e FL showed higher classification performance for AUC, SEN, and NPV (AUC: 0.8098, ACC: 0.7503, SEN: 0.8750, SPE: 0.7445, PPV: 0.1367, NPV: 0.9923). Specifically, MedMGF+ e FL obtained an increase of 29.88% in AUC, and 84.94% in SEN when compared to LR.

For both GCN+BCE and GCN+FL, we observed that there was no effective learning for the minority class. However, integrating with balancing parameter, \(\alpha\) , improved the results. \(\alpha\) FL (AUC: 0.7717, ACC: 0.8144, SEN:0.7250, SPE: 0.8185, PPV: 0.1559, NPV: 0.9847) gave a slightly higher performance than \(\alpha\) BCE (AUC: 0.7712, ACC: 0.8133, SEN: 0.7250, SPE: 0.8173, PPV: 0.1551, NPV: 0.9847), though the difference was not considered significant. Compared to the \(\alpha\) FL, the proposed MedMGF+ e FL framework demonstrated a 3.81% increase in AUC and a 15% increase in SEN.

Model performance comparison with different loss functions & SMOTE

Using BCE and FL alone does not lead to effective learning during training due to the extreme imbalance ratio of the dataset. Performance improvements were only achieved with the inclusion of SMOTE. The GCN+SMOTE+FL model (AUC: 0.7510, ACC: 0.8431, SEN: 0.6500, SPE: 0.8520, PPV: 0.1688, NPV: 0.9814) yielded better results compared to GCN+SMOTE+BCE (AUC: 0.6665, ACC: 0.7271, SEN: 0.6000, SPE: 0.7329, PPV: 0.0941, NPV: 0.9754).When compared with GCN+SMOTE+FL, the MedMGF+ e FL model showed a 5.88% increase in AUC and a 22.5% increase in SEN, although there was a decrease of 8.05% in SPE and 3.21% in PPV. Additionally, MedMGF+ e FL achieved a 3.58% increase in AUC and a 4.98% increase in SEN when compared to LR+SMOTE.

Model performance comparison for the proposed loss function

We observed that MedMGF achieved high SEN ( \(\alpha\) BCE: 0.8750, \(\alpha\) FL: 0.8250, e FL: 0.8750), high AUC ( \(\alpha\) BCE: 0.7975, \(\alpha\) FL: 0.7998, e FL: 0.8098), and high NPV ( \(\alpha\) BCE: 0.9896, \(\alpha\) FL: 0.9897, e FL: 0.9923) when compared to all baseline models. The best SEN (0.8750), AUC (0.8098), and NPV (0.9923) were achieved with the proposed loss function e FL. However, MedMGF+ e FL experienced a decrease in PPV (0.1367) and SPE (0.7445) compared to the other two models.

The data embedding transformation during training with MedMGF+ e LF, GCN+ \(\alpha\) FL, and GCN+ \(\alpha\) BCE. Yellow dots represent positive samples and purple dots represent negative samples

Figure 6 presents the final patient embeddings within the patient network, generated by the proposed MedMGF+ e FL framework, alongside GCN+ \(\alpha\) FL and GCN+ \(\alpha\) BCE. In this visualization, yellow dots represent the positive class, while purple dots represent the negative class. For MedMGF+ e FL, we observed that the yellow dots initially intermingle with the purple dots, making it challenging to establish a clear boundary between them. However, as training progresses, the yellow dots gradually cluster together, and by epoch 700, most of them have concentrated at one end, facilitating easier classification. In contrast, the other two baseline models quickly separated the dots, but the separation process slowed down starting from epoch 300 for GCN+ \(\alpha\) FL and from epoch 400 for GCN+ \(\alpha\) BCE. Learning in these models ceased around epoch 500, whereas it continued with MedMGF+ e FL, leading to a higher SEN for MedMGF+ e FL.

In this study, we propose a novel multi-level graph-based framework designed to represent clinical knowledge that can be utilized for several downstream applications. It consists of three components: a tree structure that captures an individual patient’s medical information, a patient-patient network, and an modified loss function specifically for imbalanced datasets. The integration of patient medical profiles and patient networks within a unified architecture facilitates multiple types of analyses, including patient stratification and cohort discovery. Our results demonstrated the framework’s effectiveness, achieving improved classification performance on a highly imbalanced pediatric sepsis dataset (imbalance ratio of 0.047) compared to baseline models. Furthermore, the proposed loss function has shown improvements in classification performance over BCE and FL. In the following section, we will discuss the framework’s properties, its clinical implications, as well as its limitations and potential direction for future research.

Framework approach . Our approach focuses on preserving the EHR’s inherent structure and interpretability by leveraging its existing groupings. By utilizing this structure and organizing it in a tree-like manner, we effectively reduce the dimensionality of the data input while maintaining a minimum level of data embedding interpretation. This dimensionality reduction leads to faster training times and a less complex learning process. The approach has also been designed to facilitate the integration of domain experts’ knowledge, allowing them to construct the structure intuitively, thereby enhancing interpretability. Compared to the creation of graphical models like Bayesian networks [ 26 ] by domain experts, constructing a tree structure is simpler and more cost-effective. Through this graph-based architecture, we can visually represent both the patient’s medical profile and their relationships with other patients. This architecture incorporates several layers of information, including interval data and hospitalization records. Essentially, it encompasses the entire hospitalization of the patient and the data for each visit in a compact, easily visualized format. Depending on the context, this can be presented either as an individual medical profile or as a cluster of similar patients. Furthermore, by integrating patient medical profiles and patient networks into a unified architecture and training process, we achieve a reduction in training costs.

Framework properties . MedMGF has the following key properties: (1) generality and modality, (2) multi-purpose functionality, (3) intuitive interpretation, and (4) minimal data processing requirements.

Firstly, the framework is designed to seamlessly integrate with various types of medical data by embedding and extending the number of modules to accommodate additional data sources. This modular approach allows for the effortless incorporation of new information, enabling the framework to be easily modified and updated in response to evolving medical data. With its flexible module structure, the MedMGF framework efficiently utilizes available information, enhancing its adaptability and scalability.

Secondly, the framework demonstrates potential for a wide range of tasks, such as disease diagnosis, cohort discovery, and risk prediction. For instance, the similarity between patient profiles can be leveraged to predict another patient’s risk of rehospitalization or their likely response to treatment. Clinicians can also utilize the framework to identify individuals at risk for certain diseases or adverse reactions by comparing medical profiles. Additionally, MedMGF can serve as a bedside monitoring system, tracking patients’ conditions and the progression of their diseases. In some scenarios, the framework could be adapted to alert clinicians when a patient’s medical profile closely resembles that of a specific disease or when certain characteristics are present, enhancing early detection and intervention.

A third characteristic of the framework is its ease of interpretation, which enables clinicians to easily understand concepts related to the structure of the EHR, patient profiles, and the patient network. By presenting the data in a clear and concise manner, the framework can assist clinicians in making informed decisions and gaining valuable insights from framework visualizations. This intuitive interpretability enhances the framework’s effectiveness and usability in various medical contexts, ultimately contributing to improved patient care and outcomes.

Last but not least, it requires minimal processing of EHR data since it does not require oversampling techniques to improve learning, or additional processing to map data to the multilevel graph-based structure. However, it still requires basic processing tasks such as handling missing data, removing outliers, and selecting variables for the EHR tree-based structure.

Handling data imbalance . Class imbalances in medical data are common and can significantly impair classification performance [ 27 , 28 ].Due to these imbalances, ML models may struggle to accurately differentiate between classes, often leading to biased predictions that favor the dominant class. Various techniques can address this issue at both the data and algorithmic levels. Data-level approaches include oversampling and undersampling, while algorithmic-level approaches involve heuristics that prioritize minority classes [ 29 ].

Oversampling techniques, such as SMOTE, have shown effectiveness in improving ML model performance by generating synthetic samples during training. This, however, may introduce unwanted additional noise and bias to the training process. On the other hand, undersampling, which reduces the number of samples in the dominant class, is not beneficial when dealing with extremely imbalanced or small medical datasets. In this study, we address the imbalance problem at the algorithmic level by modifying the focal loss function. By assigning a modulating term to samples, the loss function can concentrate more on hard-to-classify samples during training. The modulating term proposed in our study creates a flexible sampling weight that adapts based on the framework’s learning at each training round, eliminating the need to rely on a hyperparameter.

Framework explainability . It is essential for clinicians to understand how machine learning models make decisions to apply these models to their practice. For this reason, models should be able to explain how data is used, identify the factors influencing decisions, and clarify how those decisions are reached. Given this need, it is not surprising that Explainable AI (XAI) has seen rapid growth in recent years [ 30 , 31 , 32 ]. XAI plays a critical role in bridging the gap between proof-of-concept studies and applied ML in medicine [ 33 ]. By leveraging XAI, potential biases or errors in the model can be identified, offering insights into the reasons behind specific decisions. Moreover, it can be used to tune parameters or correct errors in the model. XAI techniques commonly used in ML-based studies include Shapley Additive Explanations (SHAP, [ 34 ]) and Local Interpretable Model-Agnostic Explanations (LIME, [ 30 ]). Currently, our framework does not use XAI, but it can easily be adapted to do so. For example, it is possible to identify different nodes’ attention weights with SHAP or LIME or with Graph Attention Networks (GAT, [ 35 ]) integrated into the framework. An alternative is to integrating a GAT-like approach to the hierarchical embeddings to enhance its explainability during the model learning.

Framework complexity . The framework consists of four operations: (1) the tree-structure representation and embedding for EHR data \(\mathcal {O}_{\mathcal {T}}\) , (2) the multilevel data embedding for patient’s medical profile \(\mathcal {O}_{\mathcal {P}}\) , (3) the construction of patient-patient medical profile network \(\mathcal {O}_{\mathcal {G}}\) , and (4) inference for downstream tasks on the medical profile network \(\mathcal {O}_{\mathcal {I}}\) . Hence, the time complexity of the overall framework will be the sum of these operations:

The patient’s medical profile network is constructed based on a Euclidean distance matrix \(\in \mathbb {R}^{N \times N}\) with N number of patients. Hence, the complexity is estimated to be \(\mathcal {O}(N^2)\) . The core operation in (1), (2), and (4) is based on the message passing mechanism. This mechanism includes the feature transformation, neighborhood aggregation, and updating via activation function in both forward and backward pass for one layer. In the forward pass, the feature transformation is a multiplication between node feature matrix \(X \in \mathbb {R}^{N \times T}\) and transformation weight matrix \(W \in \mathbb {R}^{T \times T}\) , hence, \(\mathcal {O}(NT^2)\) . Neighbor aggregation is a multiplication between matrices of size \(N \times N\) and \(N \times T\) , yielding \(\mathcal {O}(N^2T)\) . Finally, the cost for using activation function is a \(\mathcal {O}(N)\) . In practice, we could use a sparse operator, therefore the cost of the neighbor aggregation can be reduce to \(\mathcal {O}(|E|T)\) . Hence, the total cost of the forward pass is \(\mathcal {O}(NT^2) + \mathcal {O}(|E|T) + \mathcal {O}(N)\) . In the backward pass, the cost of performing the backprobagation for X and W is \(\mathcal {O}(NT^2) + \mathcal {O}(|E|T)\) .

In the tree-structure representation \(\mathcal {T}\) for EHR data, there are \((|\mathcal {P}-1|)\) message passing and one aggregation operation at the root node. Additionally, the multilevel data embedding for interval and hospitalizations consist of three aggregation functions. Hence, the time complexity of the framework from the four mentioned operations is:

As we used embedding to reduce the dimension of the feature vectors, T is rather small compared to the original dimension of the feature vectors. Therefore, overall complexity of MedMGF is reduced to \(\mathcal {O}(N^2)\) . The complexity depends on the number of sample in the dataset. As the number of sample grows, it will be taxing to construct the patient network.

Comparison with previous studies . Table 6 provides a summary of our proposed framework, MedMGF, in comparison with MiME, GRAM, and MDP, all of which employ a multi-level embedding approach to medical data representation. While MiME and GRAM may be limited to diagnosis and treatment codes, MedMGF encompasses more aspects of EHR data and can be extended to incorporate imaging, signals, and other data types into the representation. Although MDP integrated clinical data into GRAM, the data is still handled in a flat manner. While existing works exploit the hierarchy between medical codes, MedMGF exploits the hierarchy between EHR data itself. MiME and GRAM are capable of representing complex and general medical concepts beyond just data alone.

All methods are capable of handling both small and large medical datasets. With MedMGF, the complexity increases significantly as the number of patients increases. None of the methods have integrated XAI, with model interpretation primarily derived from the framework architecture. GRAM and MDP are notable for their use of attention mechanisms, which allow for better model interpretation and feature importance determination. In this regard, MedMGF relies on the intuitive tree structure of EHR data as well as the integration of a network of patient similarity to enhance the interpretation of the model. As of now, MedMGF does not have a mechanism for determining the importance of features.

In comparison with existing methods, MedMGF has the advantage of handling imbalanced data and does not require additional data processing. Existing methods do not address imbalanced data directly and may require additional steps to process medical codes when applied to other EHR datasets.

Clinical impact . The MedMGF framework demonstrates significant improvements in AUC and SEN when compared to the baseline models on an extremely imbalanced dataset. The improvement in these metrics suggests that MedMGF may improve diagnostic precision and accuracy in real-world medical settings, such as sepsis diagnosis, where the sepsis population is much smaller than the healthy population. Furthermore, a false negative in a sepsis diagnosis can have a more detrimental effect on the patient’s well-being than a false positive. It is therefore more desirable to achieve a high level of performance in SEN to reduce the number of false negatives. It cannot be ignored that false positives can result in a greater incidence of antibiotic resistance. However, the well-being of the patient as well as his or her mortality status should usually take precedence. Our MedMGF framework is therefore advantageous, since it can deliver a high SEN on imbalanced data. By effectively addressing the challenges posed by imbalanced datasets, MedMGF can potentially open up new possibilities for more accurate and reliable clinical applications. In terms of development, deployment, and application, MedMGF can be tailored to meet a variety of needs in the hospital, including disease diagnosis, bedside monitoring, and research assistance. With its versatility, it can be used for a variety of purposes, thereby eliminating the need for multiple systems and frameworks, resulting in cost savings.

Study limitation & future works . There are, however, a number of limitations to our study. First, the limited number of datasets used for evaluation may raise concerns about MedMGF’s generalizability, which is an important aspect of ML to ensure that the model can perform well on unseen data. Without a diverse range of datasets, the model may fail to accurately predict outcomes in real-world scenarios, leading to unreliable results and limited practical applications. Second, for demonstration purposes, we used only a portion of the data collected within 24 hours of ICU admission. To validate the generality of the framework when modeling patient medical profiles with several hospitalizations and intervals, more data points should be included. The number of features in the dataset is relatively small to be able to validate the complexity of the framework, as discussed in the section on complexity analysis. As our experiment only work on EHR data, more research should be conducted to validate on other data types (e.g., imaging, waveforms).

Furthermore, a comparison of our work with previous studies would provide additional evidence and validation of the MedMGF’s efficiency. However, previous studies such as MiME and Med2Vec require data on the relationship between symptoms and treatments, which is not available in our dataset. The implementation of MiME or GRAM with our current data is therefore challenging. We did not include the performance results of MedMGF with MiME, GRAM, and MDP in our comparison for the following reasons. Each framework uses different performance metrics to measure the performance: MiME uses PR-AUC for predicting the onset of Heart Failure (HF), GRAM uses Accuracy@K (where K represents the top diagnosis code guesses of the next hospital visit) to count the number of correct-predicted codes and AUC for predicting the onset of HF, MDP measures Accuracy@K for the top k diagnosis code guesses of the next hospital visit, our MedMGF uses AUC, ACC, SEN, SPE, NPV, PPV for sepsis prediction. Considering the differences in nature of the tasks defined in the various experiments and the metrics used, it is challenging for us to compare the results among studies. In addition, we were not able to reproduce MiME or GRAM as our dataset lacks the relationship between treatment and diagnosis codes.

In addition, the inferred characteristics of the framework are inferred from its design. Currently, demonstrating modality characteristics is challenging due to our dataset lacking imaging or waveform data. Therefore, more research is needed to confirm the feasibility of the framework for a variety of other analysis purposes as well as to confirm its multipurpose characteristic. Finally, we have not yet incorporated an XAI mechanism into the framework. To address these limitations, future research can consider collecting data over a longer period in order to conduct evaluations that are more comprehensive and diverse. Additionally, incorporating data from multiple healthcare institutions or collaborating with other researchers could enhance the framework’s generalizability and validate its effectiveness across different settings. It is also beneficial to integrate an XAI mechanism into the framework in order to enhance its interpretability. XAI is an emerging area in applied ML within healthcare, and it has the potential to significantly enhance model interpretation and promote the practical ML application in clinical settings. Literature reviews and model development related to XAI and the contribution of various types of medical data to clinical prediction models, could be valuable areas for further research.

Our study proposes MedMGF, a framework that integrates medical profile representation and patient-patient profile network within a single architecture. It utilizes the hierarchical structure of EHR data to represent the patients’ medical data and the graphical structure of patient-patient networks to perform supervised tasks. Additionally, the proposed modification to the focal loss resulted in improved classification performance on imbalance datasets compared to the baseline models. Generally, the framework encapsulates both generality and modality that can easily be adapted to a variety of analyses and applications. Furthermore, it can be further extended by incorporating XAI to enhance its interpretation and transparency in future research.

Availability of data and materials

The datasets analysed during the current study are available in the PhysioNet repository, https://physionet.org/content/picdb/1.1.0/ .

Code availability

The underlying code for this study is not publicly available but may be made available to qualified researchers on reasonable request from the corresponding author. Link: https://github.com/zoetmn/med-mgf .

Wang W, Ferrari D, Haddon-Hill G, Curcin V. Electronic Health Records as Source of Research Data. In: Machine Learning for Brain Disorders, vol. 197. Springer US; 2023. pp. 331–354. https://doi.org/10.1007/978-1-0716-3195-9_11 . https://link.springer.com/10.1007/978-1-0716-3195-9_11 .

Kim MK, Rouphael C, McMichael J, Welch N, Dasarathy S. Challenges in and Opportunities for Electronic Health Record-Based Data Analysis and Interpretation. Gut Liver. 2024;18. https://doi.org/10.5009/gnl230272 .

Habehh H, Gohel S. Machine learning in healthcare. Curr Genomics. 2021;22:291–300. https://doi.org/10.2174/1389202922666210705124359 . https://www.eurekaselect.com/194468/article

Amirahmadi A, Ohlsson M, Etminani K. Deep learning prediction models based on EHR trajectories: a systematic review. J Biomed Inform. 2023;144:104430. https://doi.org/10.1016/j.jbi.2023.104430 . https://linkinghub.elsevier.com/retrieve/pii/S153204642300151X

Pai S, Bader GD. Patient Similarity Networks for Precision Medicine. J Mol Biol. 2018;430:2924–38. https://doi.org/10.1016/j.jmb.2018.05.037 . https://linkinghub.elsevier.com/retrieve/pii/S0022283618305321

Parimbelli E, Marini S, Sacchi L, Bellazzi R. Patient similarity for precision medicine: A systematic review. J Biomed Inform. 2018;83:87–96. https://doi.org/10.1016/j.jbi.2018.06.001 . https://linkinghub.elsevier.com/retrieve/pii/S1532046418301072

Navaz AN, T El-Kassabi H, Serhani MA, Oulhaj A, Khalil K. A Novel Patient Similarity Network (PSN) Framework Based on Multi-Model Deep Learning for Precision Medicine. J Personalized Med. 2022;12:768. https://doi.org/10.3390/jpm12050768 .

Roque FS, Jensen PB, Schmock H, Dalgaard M, Andreatta M, Hansen T, et al. Using electronic patient records to discover disease correlations and stratify patient cohorts. PLoS Comput Biol. 2011;7. https://doi.org/10.1371/journal.pcbi.1002141 .

Lu H, Uddin S. A weighted patient network-based framework for predicting chronic diseases using graph neural networks. Sci Rep. 2021;11. https://doi.org/10.1038/s41598-021-01964-2 .

Panahiazar M, Taslimitehrani V, Pereira NL, Pathak J. Using EHRs for Heart Failure Therapy Recommendation Using Multidimensional Patient Similarity Analytics. Stud Health Technol Inform. 2015;210:369–73.

PubMed   PubMed Central   Google Scholar  

Lin TY, Goyal P, Girshick R, He K, Dollár P. Focal Loss for Dense Object Detection. 2018. arXiv:1708.02002 .

Kipf TN, Welling M. Semi-Supervised Classification with Graph Convolutional Networks. 2017. arXiv:1609.02907 . Accessed 24 June 2024.

Shannon CE. A Mathematical Theory of Communication. Bell Syst Tech J. 1948;27:379–423. https://doi.org/10.1002/j.1538-7305.1948.tb01338.x . https://ieeexplore.ieee.org/document/6773024

Chawla NV, Bowyer KW, Hall LO, Kegelmeyer WP. SMOTE: Synthetic Minority Over-sampling Technique. J Artif Intell Res. 2002;16:321–57. https://doi.org/10.1613/jair.953 . https://www.jair.org/index.php/jair/article/view/10302

Mukherjee P, Humbert-Droz M, Chen JH, Gevaert O. SCOPE: predicting future diagnoses in office visits using electronic health records. Sci Rep. 2023;13:11005. https://doi.org/10.1038/s41598-023-38257-9 . https://www.nature.com/articles/s41598-023-38257-9

Grout R, Gupta R, Bryant R, Elmahgoub MA, Li Y, Irfanullah K, et al. Predicting disease onset from electronic health records for population health management: a scalable and explainable Deep Learning approach. Front Artif Intell. 2024;6:1287541. https://doi.org/10.3389/frai.2023.1287541 . https://www.frontiersin.org/articles/10.3389/frai.2023.1287541/full

Choi E, Bahadori MT, Searles E, Coffey C, Sun J. Multi-layer Representation Learning for Medical Concepts. 2016. arXiv:1602.05568 .

Choi E, Bahadori MT, Song L, Stewart WF, Sun J. GRAM: Graph-based Attention Model for Healthcare Representation Learning. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM; 2017. pp. 787–795. https://doi.org/10.1145/3097983.3098126 . https://dl.acm.org/doi/10.1145/3097983.3098126 .

Choi E, Xiao C, Stewart WF, Sun J. MiME: Multilevel Medical Embedding of Electronic Health Records for Predictive Healthcare. 2018. arXiv:1810.09593 .

Li R, Ma F, Gao J. Integrating Multimodal Electronic Health Records for Diagnosis Prediction. AMIA Annual Symposium proceedings, vol. 2021. AMIA Symposium; 2021. pp. 726–735.

Charoenphakdee N, Vongkulbhisal J, Chairatanakul N, Sugiyama M. On Focal Loss for Class-Posterior Probability Estimation: A Theoretical Perspective. 2020. arXiv:2011.09172 .

Mukhoti J, Kulharia V, Sanyal A, Golodetz S, Torr PHS, Dokania PK. Calibrating Deep Neural Networks using Focal Loss. 2020. arXiv:2002.09437 .

Ghosh A, Schaaf T, Gormley MR. AdaFocal: Calibration-aware Adaptive Focal Loss. 2023. arXiv:2211.11838 .

Zeng X, Yu G, Lu Y, Tan L, Wu X, Shi S, et al. PIC, a paediatric-specific intensive care database. Sci Data. 2020;7:14. https://doi.org/10.1038/s41597-020-0355-4 . http://www.nature.com/articles/s41597-020-0355-4

Nguyen TM, Poh KL, Chong SL, Lee JH. Effective diagnosis of sepsis in critically ill children using probabilistic graphical model. Transl Pediatr. 2023;12:538–51. https://doi.org/10.21037/tp-22-510 .

Andersen SK. Probabilistic reasoning in intelligent systems: Networks of plausible inference. Artif Intell. 1991;48:117–24. https://doi.org/10.1016/0004-3702(91)90084-W . https://linkinghub.elsevier.com/retrieve/pii/000437029190084W

Thabtah F, Hammoud S, Kamalov F, Gonsalves A. Data imbalance in classification: Experimental evaluation. Inf Sci. 2020;513:429–41. https://doi.org/10.1016/j.ins.2019.11.004 . https://linkinghub.elsevier.com/retrieve/pii/S0020025519310497

Johnson JM, Khoshgoftaar TM. Survey on deep learning with class imbalance. J Big Data. 2019;6:27. https://doi.org/10.1186/s40537-019-0192-5 . https://journalofbigdata.springeropen.com/articles/10.1186/s40537-019-0192-5

Rezvani S, Wang X. A broad review on class imbalance learning techniques. Appl Soft Comput. 2023;143:110415. https://doi.org/10.1016/j.asoc.2023.110415 . https://linkinghub.elsevier.com/retrieve/pii/S1568494623004337

Ribeiro MT, Singh S, Guestrin C. “Why Should I Trust You?”: Explaining the Predictions of Any Classifier. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Francisco California USA: ACM; 2016. pp. 1135–1144. https://doi.org/10.1145/2939672.2939778 . https://dl.acm.org/doi/10.1145/2939672.2939778 .

Ali S, Abuhmed T, El-Sappagh S, Muhammad K, Alonso-Moral JM, Confalonieri R, et al. Explainable Artificial Intelligence (XAI): What we know and what is left to attain Trustworthy Artificial Intelligence. Inf Fusion. 2023;99:101805. https://doi.org/10.1016/j.inffus.2023.101805 . https://linkinghub.elsevier.com/retrieve/pii/S1566253523001148

Saeed W, Omlin C. Explainable AI (XAI): A systematic meta-survey of current challenges and future opportunities. Knowl-Based Syst. 2023;263:110273. https://doi.org/10.1016/j.knosys.2023.110273 . https://linkinghub.elsevier.com/retrieve/pii/S0950705123000230

S Band S, Yarahmadi A, Hsu CC, Biyari M, Sookhak M, Ameri R, et al. Application of explainable artificial intelligence in medical health: A systematic review of interpretability methods. Inform Med Unlocked. 2023;40:101286. https://doi.org/10.1016/j.imu.2023.101286 . https://linkinghub.elsevier.com/retrieve/pii/S2352914823001302 .

Lundberg S, Lee SI. A Unified Approach to Interpreting Model Predictions. 2017. arXiv:1705.07874 .

Veličković P, Cucurull G, Casanova A, Romero A, Lió P, Bengio Y. Graph Attention Networks. 2018. arXiv:1710.10903 .

Download references

Acknowledgements

This study received no funding.

Author information

Authors and affiliations.

Department of Industrial Engineering and Management, National University of Singapore, Singapore, 117576, Singapore

Tuong Minh Nguyen & Kim Leng Poh

Children’s Emergency, KK Women’s and Children’s Hospital, Singapore, 229899, Singapore

Shu-Ling Chong

SingHealth-Duke NUS Paediatrics Academic Clinical Programme, Duke-NUS Medical School, Singapore, 169857, Singapore

Shu-Ling Chong & Jan Hau Lee

Children’s Intensive Care Unit, KK Women’s and Children’s Hospital, Singapore, 229899, Singapore

Jan Hau Lee

You can also search for this author in PubMed   Google Scholar

Contributions

The concept and architecture were designed by TMN under the supervision of PKL, JHL and SLC. PKL provided the technical guidance. JHL and SLC provided clinical interpretation of the results. All authors contributed to manuscript preparation, writing, critical revisions, and have read and approved the final manuscript.

Corresponding author

Correspondence to Tuong Minh Nguyen .

Ethics declarations

Ethics approval and consent to participate.

The Institutional Review Board of National University of Singapore approved this study (IRB: NUS-IRB-2024-396).

Consent for publication

This paper did not include any individual data, rights and permissions. Not applicable.

Competing interests

The authors declare no competing interests.

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplementary Information

Supplementary material 1., rights and permissions.

Open Access This article is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License, which permits any non-commercial use, sharing, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if you modified the licensed material. You do not have permission under this licence to share adapted material derived from this article or parts of it. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by-nc-nd/4.0/ .

Reprints and permissions

About this article

Cite this article.

Nguyen, T., Poh, K., Chong, SL. et al. Med-MGF: multi-level graph-based framework for handling medical data imbalance and representation. BMC Med Inform Decis Mak 24 , 242 (2024). https://doi.org/10.1186/s12911-024-02649-2

Download citation

Received : 24 May 2024

Accepted : 23 August 2024

Published : 02 September 2024

DOI : https://doi.org/10.1186/s12911-024-02649-2

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Pediatric sepsis
• Patient network
• Graphical models
• Message passing
• Machine learning

BMC Medical Informatics and Decision Making

ISSN: 1472-6947

• General enquiries: [email protected]

This week: the arXiv Accessibility Forum

Help | Advanced Search

Computer Science > Machine Learning

Title: large-scale demand prediction in urban rail using multi-graph inductive representation learning.

Abstract: With the expansion of cities over time, URT (Urban Rail Transit) networks have also grown significantly. Demand prediction plays an important role in supporting planning, scheduling, fleet management, and other operational decisions. In this study, we propose an Origin-Destination (OD) demand prediction model called Multi-Graph Inductive Representation Learning (mGraphSAGE) for large-scale URT networks under operational uncertainties. Our main contributions are twofold: we enhance prediction results while ensuring scalability for large networks by relying simultaneously on multiple graphs, where each OD pair is a node on a graph and distinct OD relationships, such as temporal and spatial correlations; we show the importance of including operational uncertainties such as train delays and cancellations as inputs in demand prediction for daily operations. The model is validated on three different scales of the URT network in Copenhagen, Denmark. Experimental results show that by leveraging information from neighboring ODs and learning node representations via sampling and aggregation, mGraphSAGE is particularly suitable for OD demand prediction in large-scale URT networks, outperforming reference machine learning methods. Furthermore, during periods with train cancellations and delays, the performance gap between mGraphSAGE and other methods improves compared to normal operating conditions, demonstrating its ability to leverage system reliability information for predicting OD demand under uncertainty.

Submission history

Access paper:.

• Other Formats

References & Citations

• Google Scholar
• Semantic Scholar

BibTeX formatted citation

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .