\section{Introduction}
\label{INTRO}

Parallel computing is often traced to the {\em D825} multiprocessor system in the 1960s ~\cite{D825_1962}, and distributed systems to early computer networks and client-server computing in the 1970s \cite{tanenbaum2016}. Concurrent programming also became commonplace around the same time-frame, with synchronizing communicating processes formalized by Disjktra~\cite{THE} and Hoare~\cite{CSP}. Nowadays, much of the dramatic advances in a wide range of disciplines are enabled by parallel and distributed computing (PDC). For example, Internet of Things (IoT) provides the basis for computing devices of heterogeneous nature, technology, and capability to cooperate and deliver added value services across diverse industries. Mobile healthcare, industrial automation, holographic teleportation, autonomous vehicles, smart environments, digital currency mining, and GPU computing in general are examples of systems enabled by revolutionary advances in communications and parallel computing~\cite{9145564}.  Such systems are founded by services that inherently need parallel processing, inter-service communication, and distributed monitoring and control.

 Given the state of today's computing, it is crucial that computing professionals understand PDC intimately, and for computing education programs to incorporate PDC concepts, not just at the graduate level but also at the undergraduate level. Although awareness of the need for PDC education has existed for more than a decade,  computing education has been slow at formalizing this need and making it actionable. In the case of the dominant Computer Science (CS) discipline, the ACM and IEEE Computer Society took some initial steps in the CS2013~\cite{CS2013} curricular guidelines to highlight the importance of PDC as one of the core tier-1 and tier-2 areas. Moreover, the guidelines expected additional coverage of PDC concepts intrinsic to operating systems, computer architecture, database management systems, and computer networks. More recently, the visionary CC2020 described draft PDC competencies for CS~\cite[pp. 112--123]{CC2020final}.

Despite these developments, many computer science programs have not paid sufficient attention to including PDC in their curricula, and ultimately preparing graduates to meet today's needs despite the availability of textbooks~\cite{kirk,quinn}, as well as extensive curricular resources developed by the Center for Parallel and Distributed Curriculum Development and Educational Resources (CDER)~\cite{CDER},  PDC~Unplugged~\cite{PDCUnplugged}, and researchers \cite{PrasadText,Fernandez2019,Olivera2019,Homma2008:HPC,ToUCH}.

Recognizing these professional needs, as well as the lack of sufficient incentives, ABET's~\cite{ABET} Computing Accreditation Commission (CAC) revised its criteria for undergraduate Computer Science programs by requiring coverage of PDC concepts~\cite{CACCriteria}. These criteria were first released in 2018, and since 2019, all ABET-accredited CS programs are required to include PDC in their curricula. As ABET typically follows a six-year review cycle, it is likely that all [currently] 398 ABET-accredited CS programs will have coverage of PDC content by 2024.

This paper explores the impact of the revised ABET's CS Program Criteria on the incorporation of  PDC content into modern ABET-accredited computer science programs. Section~\ref{Role} discusses the history and formulation of the PDC requirements in the ABET CAC Criteria, along with approaches to covering PDC not only to meet the ABET CAC Criteria requirements, but also to enhance them. Section~\ref{survey} presents the results of a survey of top ABET-accredited CS programs to understand how they support PDC concepts across their curricula. Using three examples of ABET-accredited programs, Section~\ref{CS CASE STUDIES} expands on actual implementation of the different approaches to satisfy the PDC requirements of the CAC Criteria. Section~\ref{PDCENG} explores whether the ABET engineering criteria~\cite{EACCriteria}, along with the ACM/IEEE Computer Society curricular guidelines for computer engineering~\cite{ACM_CE} and software engineering~\cite{ACM_SE}, essentially require coverage of PDC concepts to ensure that graduates are prepared to enter engineering practice. The paper concludes with remarks about how PDC coverage can be improved in computing and engineering programs.
\section{Using Accreditation to Move PDC Forward}
\label{Role}

The world of accreditation differentiates between {\em institutional accreditation} where regional or national accreditation organizations provide assurance that a university as a whole reliably provides quality education and {\em program accreditation} where accrediting bodies use disciplinary guidelines to establish and verify the quality of the degree program and increasingly, the characteristics of the program graduates~\cite{Oudshoorn2018:ASEE}. Program-level accreditation focuses on areas such as student advising, graduation requirements, faculty qualifications, curriculum standards, and available facilities. In the US (and over 40 other countries), ABET~\cite{ABET} has been the accrediting body for programs in computing and engineering, through its Computing Accreditation Commission (CAC) and Engineering Accreditation Commission (EAC). The rest of this section examines PDC requirements in the CAC Criteria, specifically Computer Science; Section~\ref{PDCENG} explores PDC in Software Engineering and Computer Engineering.

\subsection{ABET's Computer Science Accreditation Criteria}
\label{CS Criteria}

ABET's program criteria across all its commissions are created by the professional society representing the corresponding discipline. For instance, for computing disciplines including computer science, the professional society is CSAB, the joint body created by ACM and IEEE Computer Society~\cite{CSAB}. As mentioned earlier, the ACM and IEEE Computer Society have jointly developed different curricular guidelines for a variety of computing disciplines. In the case of CS, the 2013 ACM/IEEE Computer Society's Computer Science Curricular Guidelines (CS2013)~\cite{CS2013} have been the latest. These guidelines highlighted the importance of parallel and distributed computing and noted that ``parallel and distributed computing has moved from a largely elective topic to become more of a core component of undergraduate computing curricula."

Therefore, the accreditation criteria for CS developed by ABET draw substantially from CS2013~\cite{CS2013}, which defines parallel and distributed computing to encompass the following~\cite{CS2013}:

\begin{enumerate}
    \item  An understanding of fundamental systems concepts such as concurrency and parallel execution, consistency in state/memory manipulation, and latency.

     \item Understanding of parallel algorithms, strategies for problem decomposition, system architecture, detailed implementation strategies, and performance analysis and tuning.

    \item Message-passing and shared-memory models of computing.
\end{enumerate}

CC2020~\cite{CC2020final} reiterates the above knowledge areas and recommends specific topics including a coverage of a parallel divide-and-conquer algorithm, critical path, race conditions, processes, deadlocks, and properly synchronized queues.

What follows  examines how PDC is required by the CAC Criteria for accrediting Computer Science programs and what approaches can be used by accredited programs to meet this requirement.

Program-level accreditation of Computer Science (CS) programs has been ongoing since the 1985-86 academic year.  At present, the CAC accredits 398 CS programs around the globe using the {\em ABET Criteria for Accrediting Computing Programs (Criteria)}~\cite{CACCriteria}. The CS Criteria comprise the {\em General Criteria} that apply to all computing programs and the {\em Computer Science Program Criteria} that are specific to CS programs.

\begin{figure}[tb]
\centering
\fbox{
\parbox{0.9\columnwidth}{
$\ldots$\\
The curriculum requirements specify topics, but do not prescribe specific courses.  For CS, the requirements are: at least 40 semester credit hours (or equivalent) that must include (among several other topics):
\begin{itemize}
\item $\ldots$
\item Exposure to computer architecture and organization, information management, networking and communication, operating systems, and {\bf parallel and distributed computing}.
\item $\ldots$
\end{itemize}
}
}
\caption{Computer Science Program Criteria---Curriculum}
\label{fig:cs criteria}
\end{figure}

This paper focuses on the CS programs because they are now required to cover PDC by the corresponding criteria, within the curriculum requirements, as depicted in Fig.~\ref{fig:cs criteria}. In other words, in line with the CS2013 curricular requirements~\cite{CS2013}, the ABET CS Program Criteria require exposure to computer architecture and organization, information management, networking and communications, operating systems, and parallel and distributed computing. The criteria explicitly point out that these requirements are flexible, and do not necessarily ask for courses to be introduced into programs, but rather topics or knowledge areas that ought to be covered somewhere in the program requirements. For example, some topics may be covered in a relatively small number of lectures embedded within an existing course.

The phrase ``exposure to" used in these criteria is in line with the CS2013 curricular requirements. With the anticipated  continued growth of PDC in computing, the authors assume the next decennial revision of the ACM CS guidelines will emphasize PDC even more. In the meantime, as discussed in the next two sections, many excellent programs in CS are already emphasizing PDC, even beyond  what the ABET CS Criteria require.

 \subsection{Meeting the PDC Exposure Requirement in the Computer Science Criteria}
\label{Meeting CS Criteria}

The Computer Science Criteria are flexible and provide several avenues for the PDC content to be included. Opportunities thus
exist across various courses within a Computer Science curriculum to include PDC exposure. For the accreditation criteria to be satisfied, a program must include PDC coverage in required coursework to ensure all  graduating students receive the required exposure. Based on curricula formulated by CDER~\cite{CDER}, three core PDC concepts have been clearly identified namely, {\em concurrency}, {\em parallelism}, and {\em distribution}~\cite{Raj2020HighPC}.
These topics can be covered in courses such as computer programming, algorithms design, operating systems, databases, networking, and architecture.

Newhall~\cite{NEWHALL201753} explored how PDC could be included when planning or revising the curriculum:
\begin{enumerate}

\item Achieve an early exposure and maturity of PDC topics to allow learners an opportunity to achieve further in-depth knowledge where needed before graduation.
\item Design a curriculum that intentionally overlaps some topics across the curriculum.
\item Provide breadth of knowledge as well as appropriate in-depth coverage.
\item Expose learners to the topics in multiple sub-disciplines as opposed to coursework that only covers PDC topics.
\end{enumerate}

Most programs follow one or both of two major approaches to incorporating any content in curricula. In the first approach, programs dedicate at least one required course to cover the required knowledge units for any required area. For PDC, such a required course would need to contain essential parallel programming concepts, as well as more advanced parallelism and distribution concepts. This content can be developed following the guidance provided by CS2013~\cite{CS2013} or the draft PDC competencies mentioned in CC2020~\cite{CC2020final}.

The dedicated-course approach is the obvious approach, as it provides faculty and students with the opportunity to explore a wide array of PDC topics while emphasizing others that may have been offered in other courses in the program. A course like this could tap into the vast amount of resources that are made available by Intel, NVIDIA, and IBM, among others, which include course materials, textbooks, free compilers, free training, and in some instances free hardware. Also, CDER~\cite{CDER} and PDC Unplugged~\cite{PDCUnplugged} provide a multitude of curricular content and labs that can be easily included.

On the other hand, due to limits imposed by faculty availability and expertise, available number of course credits, and related constraints, a program may find that it is simply not possible to add a dedicated course to the program curriculum. However, as PDC concepts are inherent in various computing areas, it is not hard to integrate different parts of the knowledge area into existing courses in the curriculum, rather than create a dedicated course. Thus, PDC coverage is supported at the periphery of the curriculum by scattering the knowledge units into various required courses. Some programs would probably find this approach more practical to satisfy accreditation requirements while providing the students with some exposure to PDC.  Table~\ref{topics} shows how a typical accredited computer science program may choose to include coverage of PDC across different courses such as Systems Programming, Computer Organization or Architecture, Operating Systems, and Database Systems.

\begin{table*}[tb]
\caption{Mapping Different PDC Concepts to Typical Courses }
\label{topics}
\begin{center}
\begin{tabular}{|l|p{1.5cm}|p{1.6cm}|p{1.2cm}|p{1.1cm}|p{1.1cm}|}
\hline
& Systems Programming & Computer Organization/ Architecture & Operating Systems & Database Systems & Computer Networks\\\hline
Programming with threads & $\times$ & & $\times$ & & $\times$\\ \hline
Transactions processing & & & &$\times$ &\\ \hline
Parallelism and concurrency & $\times$ & $\times$ & $\times$ & $\times$&$\times$\\ \hline
Shared-Memory programming & $\times$ & & $\times$ & & \\ \hline
Inter-Process Communication (IPC)& $\times$ & & $\times$ & & $\times$\\ \hline
Atomicity & $\times$ & & $\times$ & &\\ \hline
Performance measurement, speed-up, and scalability &  & $\times$ & & &\\ \hline
Multicore processors & & $\times$ &  & &\\ \hline
Shared vs. distributed memory & $\times$ & $\times$ & $\times$ &  &\\ \hline
SIMD and vector processors & &  $\times$&  & &\\ \hline
Instruction Level Parallelism & & $\times$& & &\\ \hline
Flynn’s taxonomy & & $\times$ & & & \\ \hline
Client-server programming & $\times$ &  & & &$\times$\\ \hline
Memory and caching  & $\times$ & $\times$ & $\times$ & &\\ \hline
\end{tabular}
\end{center}
\end{table*}%
\section{PDC in 20 Top Accredited CS Programs}
\label{survey}

To  understand how ABET-accredited programs have incorporated PDC in their curriculum, the authors collected data from 20 ABET-accredited computer science programs that are ranked in the top $100$ by US News~\cite{USNews}.

\begin{figure*}[tb]
\centerline{\includegraphics[width=1.25\columnwidth]{Fig/topics.pdf}}
\caption{PDC Topics Used by Surveyed Programs for ABET Accreditation}
\label{fig:topics}
\end{figure*}

\begin{figure*}[bt]
\centerline{\includegraphics[width=1.25\columnwidth]{Fig/courses.pdf}}
\caption{Courses for PDC Content by Surveyed Programs for ABET Accreditation}
\label{fig:courses}
\end{figure*}

The collected data was studied with a focus on required courses that included PDC components.  The course descriptions and the learning outcomes were analyzed using information that were published online.  A weighted sum of all courses that tackle specific components of the PDC knowledge area was computed. Fig.~\ref{fig:topics} shows  common topics covered by the surveyed programs that help to support PDC for ABET Accreditation.  Fig.~\ref{fig:courses} shows the percentage of courses that encompass these topics.  It is worth noting that out of the 20 surveyed programs, only one program had a dedicated parallel programming course while the remaining programs used multiple courses to cover PDC topics.

Most modern CS programs offer the following courses, several of which are required:
\begin{enumerate}
    \item A typical {\em operating systems} or {\em systems programming} course can include coverage of concurrency, atomicity, shared memory programming, and inter-process communication.  Programming with threads can also be covered in a more elaborate way using client-server programming in a computer networks course or in systems programming course;
    \item A {\em database management} course can incorporate distributed computing concepts including transactions processing, scheduling concurrent transactions, transactions locks, and deadlocks;
    \item A {\em computer organization} or {\em architecture} course can incorporate Amdahl’s law and its implication on the performance of a particular parallel algorithm, speed-up and scalability, Flynn's taxonomy, the concept of multicore processors, multiprocessor caches and cache coherence, pipelining, instruction level parallelism, and vector and SIMD computers. Advanced computer architecture courses can also cover concepts of shared and distributed memory;
    \item {\em Programming language} courses can incorporate support for parallel and distributed computing concepts, including but not limited to, programming with threads, programming language constructs and APIs for thread creation and management, networking to support distributed computing, inter-process communication and synchronization, along with virtual machine and translator support for parallelization;
    \item Selected parallel algorithms and related theoretical analysis and applications can be covered in a {\em design and analysis of algorithms} course;
    \item A course in {\em software engineering} can provide a coverage of modeling and notations used for parallel behavior as well as design considerations of distributed components.
\end{enumerate}

These results show--at a high level--that the ABET Computer Science criteria have already begun to have their anticipated impact on incorporating PDC concepts in undergraduate CS programs. Three different ABET-accredited CS programs on three different continents are now examined for achieving PDC coverage.
\section{Case Studies: PDC in CS Programs}
\label{CS CASE STUDIES}

This section examines three ABET-accredited computer science programs from the authors' own institutions to study the actual coverage of PDC topics.

\subsection{Case Study: Lebanese American University}

The Computer Science Program at the Lebanese American University incorporated parallel programming early in 1996 in the form of a fully-fledged course based on the Network of Workstations (NOW) model~\cite{now,Adams2015:budget:beowulfs} using the Message-Passing Interface (MPI).  The course content was later updated to include GPGPU manycore programming and a brief introduction to deep learning as a case-study to showcase the power of parallelism~\cite{CS-LAU}. It should be noted that in addition to this required course, students explore PDC concepts in various required courses including {\em operating systems}, {\em computer organization}, and {\em database management systems}.

\subsubsection{Meeting the PDC Program Criteria}

The dedicated course introduces relevant parallel architectural trends and aspects of multicores in addition to the design and analysis of parallel programs.  The course description is:
\begin{quote}
This course provides an introduction to parallel programming with a focus on multicore architectures and cluster programming techniques. Topics include relevant architectural trends and aspects of multicores, writing multicore programs and extracting data parallelism using vectors and SIMD, thread-level parallelism, task-based parallelism, efficient synchronization, program profiling, and performance tuning.  Message-passing cluster-based parallel computing is also introduced.  The course includes several programming assignments to provide students first-hand experience with programming, and experimentally analyzing and tuning parallel software.
\end{quote}

The course learning outcomes are that students will:

\begin{enumerate}
    \item Understand the challenges of as well as the motivations for using parallel programming.

    \item Demonstrate an ability to analyze the efficiency of a given parallel algorithm.

    \item Demonstrate an ability to design, analyze, and implement programming applications using multicore and manycore systems.
\end{enumerate}

In addition, students need to complete labs, a milestone project in each part, one written report per milestone, and to make one oral presentation. As the course is being used to assess communication skills, all material is graded for grammar, spelling, and style.

The course delivery is easily broken down into three parts.  The first part introduces the history of PDC and the driving forces behind its recent resurrection, tackling issues such as the continuous decrease of feature size, the increase in the number of transistors per chip, clocking, performance scalability, excessive power consumption, and the rise of multicore processors.

The second part of the course focuses mostly on multi-core programming using {\tt Pthreads} and {\tt OpenMP}.  Students are introduced to shared-memory issues including thread-level parallelism, task-based parallelism, data races, false sharing, memory contention, synchronization, and extracting data parallelism using vectors and SIMD.  This part of the course is supported by {\em Intel}, which provides hands-on labs as well as free licenses for the {\em Intel Parallel Studio} compiler.

In the third part, which is roughly 60\% of the course, students are introduced to the concept of manycores focusing on single instruction,  multiple threads (SIMT) execution model that is inherent in GPU devices.  In this part, students develop manycore applications using {\tt CUDA C} and {\tt OpenACC}, and learn advanced memory management techniques as well as using concurrent streams.  This part of the course is supported by NVIDIA's Deep Learning Institute (DLI) which provides all students access to the NVIDIA's online training platforms.  Typically, students earn two NVIDIA certificates in this part, an OpenACC and a CUDA C.  Labs are completed on the cloud using NVIDIA's accelerated computing environment.

The parallel programming course  is also a cornerstone for meeting the ABET criteria.  In fact, the course is used to meet multiple performance criteria in ABET's Student Outcome 2 (Design, implement, and evaluate a computing-based solution to meet a given set of computing requirements in the context of the program’s discipline) and Student Outcome 3 (Communicate effectively in a variety of professional contexts), as well as the curricular requirement for PDC exposure.

\subsection{Case Study: The American University in Cairo}
\label{CS AUC}

The Computer Science and Engineering Department at the American University in Cairo offers two ABET accredited programs: one in Computer Science, and another in Computer Engineering. Both programs follow an early maturity pedagogical approach to ensure students learn key knowledge units as early as possible in the curriculum. The intent is to provide students with an ability to innovate faster, and create more meaningful contributions before graduation.

The CS program does not require a dedicated course that covers PDC topics, yet the knowledge units to support this requirement are satisfied across various other courses.
\begin{enumerate}

\item In the fundamental course sequences, students are exposed to a basic ability to create and control threads, as well as a simple client server connectivity.

\item In the courses of computer organization, and architecture, multiprocessing, thread level parallelism, pipelining, instruction level parallelism, superscalar architectures, VLIW architectures and architectures based on dynamic scheduling such a the non-speculative and the speculative versions of Tomasulo's architectures are covered.

\item The operating systems course provides coverage at a substantial depth for multi-threading, speedup, multiprocessing, mutual exclusion, synchronization, deadline and starvation, and scheduling on single and multiprocessor systems.

\item In software engineering, students are exposed to the development of semi-complex systems that involve distribution of components and some parallel functionality and  distribution of components.

\item In concepts of programming languages, design considerations for various programming languages are discussed, including support for networking, and threading. Students work on a project using one of the trending languages, and must present many of the language features including language support for  parallelism and networking, and the effect of garbage collection on currently executing processes and threads.

\item Even though there is a course dedicated to distributed systems within the department, it is only required at the moment for the Computer Engineering program. This fundamentals of distributed computing course covers topics ranging from modeling and specification to consistency and inter-process communication, load balancing, process migration, and distributed challenges. A demanding project helps students master some of the fundamental and advanced topics of the domain.
\end{enumerate}

\subsection{Case Study: Rochester Institute of Technology}
\label{CS RIT}

In 2010, i.e., almost a decade prior to the CAC Criteria requirement for PDC to be covered, the faculty in RIT's computer science program recognized that few modern computers consisted of a single box with a single CPU, and that modern computers typically include multi-core CPUs forming clusters of machines connected by a local network, or are units of distributed systems interconnected over the Internet. The faculty decided then that all computer science students needed to know not only how these these parallel and distributed systems function but also how to write programs for these computing systems. To address this goal, it was decided to create a coherent single semester-long course that would allow students learn the foundations of PDC including principles of parallel computing, basic network protocols, principles of network security, basic architectures of cluster and grid computing, and build additional depth in multithreaded programming and techniques for developing network applications.

Another important consideration was that these topics needed to be covered in a single course, so that students could understand the interrelationships between these topics, such as the synergies between multithreaded programming and network programming. The focus was not to cover these topics in depth, but instead to provide the breadth of knowledge and skills in PDC for each computer science student. The intention was that students would be ready to take advanced electives in these topics, which could include operating systems, networking, systems programming, distributed systems, parallel computing, grid computing, as well as cryptography and cybersecurity. Before this change, the program had required courses in operating systems and in networking. Obviously after the change, modified courses in operating systems and networking were created as electives to explore advanced topics in greater depth.

The course, \textit{Concepts of Parallel and Distributed Systems}, has been taught since Fall 2013 when RIT transitioned to a semester system. The course description is:
\begin{quote}
    This course is an introduction to the organization and programming of systems comprising multiple computers. Topics include the organization of multicore computers, parallel computer clusters, computing grids, client-server systems, and peer-to-peer systems; computer networks and network protocols; network security; multithreaded programming; and network programming. Programming projects will be required.
\end{quote}
The course learning outcomes are that students will:
\begin{enumerate}
    \item Explain the concepts of processes, threads, and scheduling.
    \item Develop multithreaded programs.
    \item Explain the concepts of computer networking, the layered network architecture, network security, and network communication with connections and datagrams.
    \item Develop network application programs.
    \item Explain the concepts of distributed system architectures and middleware.
    \item Explain the concepts of parallel computer architectures.
\end{enumerate}
The main topics covered in the course include the following: multithreaded computing (including processes, threads, scheduling, synchronization, deadlock, starvation. and multicore computers); networked computers (including client-server, connections, application protocol design, and socket and datagram programming); network protocols and security;  distributed systems (including different architectures, middleware, distributed objects, and web services), and parallel computing (including architectures and middleware).

In addition to this required course, students explore PDC concepts in earlier courses, starting in their second required programming course in the freshman year, where Java threads and synchronization are explored in depth. The required course, Mechanics of Programming, covers pthreads in depth. Another required course, Concepts of Computer Systems, also covers pipelining and other related PDC concepts.

\section{PDC in Computer and Software Engineering Programs}
\label{PDCENG}

ABET's engineering accreditation criteria~\cite{EACCriteria} for computer engineering (CE) and software engineering (SE)  programs do not explicitly mention PDC. They, however, do require the program curriculum to ``provide adequate content for each area, consistent with the student outcomes and program educational objectives, to ensure that students are prepared to enter the practice of engineering"~\cite{EACCriteria}. Modern curricula for these engineering programs are typically guided by the curricular guidelines developed by ACM and IEEE Computer Society's Computer Engineering~\cite{ACM_CE} and Software Engineering~\cite{ACM_SE}. In essence, any modern computer engineering or software engineering program that lives up to these curricular guidelines will need to cover PDC concepts. In other words, it is likely that ABET's engineering criteria, being based on the ACM/IEEE Computer Society curricular guidelines, require the PDC coverage through courses that are inherently required for both programs.

The computer engineering curriculum guidelines (CE2016) delineate twelve broad knowledge areas for the relevant body of knowledge~\cite{ACM_CE}. Knowledge areas are decomposed into associated knowledge units with a list of learning outcomes each. Knowledge units are classified as core and supplementary units. Core units of each knowledge area constitute its minimal required knowledge and skills that have to be covered within a program curriculum. Computing algorithms, computer architecture and organization, systems resource management, and software design represent knowledge areas of computer engineering that explicitly address parallel and distributed computing concepts through core knowledge units.

Table~\ref{tab:CE_PDC} lists the knowledge areas that cover PDC-related core knowledge units. As per CE2016, most of the pertinent skills associated with the latter knowledge units are expected to be minimally met with relatively basic ability, while a few of them are set to a higher level of accomplishment.

\begin{table}[tbh]\centering
\caption{PDC in Computer Engineering Knowledge Areas~\cite{ACM_CE}}
\label{tab:CE_PDC}
\begin{tabular}{|p{0.30\columnwidth}|p{0.55\columnwidth}|}
\hline
\textbf{Knowledge Area} & \textbf{PDC-related Core Knowledge Units}\\ \hline

Computing Algorithms & Parallel algorithms/threading \\  \hline

Architecture and Organization & Multi/Many-core architectures \\
      & Distributed system architectures \\ \hline

Systems Resource Management & Concurrent processing support\\ \hline

Software Design & Event-driven and concurrent programming \\ \hline

\end{tabular}
\end{table}

Similar to CE2016, the software engineering curriculum report SE2014 defines a body of core knowledge that represents the knowledge and skills for which there is consensus that any software engineering graduate should acquire~\cite{ACM_SE}. This core knowledge is coined as software engineering education knowledge areas and referred to as SEEK. SEEK  comprises 10 knowledge areas with a set of associated knowledge units, some of which are designated as essential in relevance to the core knowledge. CE2016 defines a collection of topics that include the cognitive skill level at which each topic of a given knowledge unit is expected to be attained. Three cognitive skill levels are defined with application being the  highest level.

As shown in Table~\ref{tab:SE_PDC}, computing essentials area is a main knowledge area of SEEK that entails the foundation for the design and construction of software and includes one unit on construction technologies. The former unit emphasizes two PDC-related topics, namely concurrency primitives and construction methods for distributed software. Both topics are classified as essential to the core and expected to be met at the application level.

\begin{table}[tbh]\centering
\caption{PDC in Software Engineering Knowledge Areas~\cite{ACM_SE}}
\label{tab:SE_PDC}
\begin{tabular}{|p{0.23\columnwidth}|p{0.65\columnwidth}|}
\hline
\textbf{Knowledge Area} & \textbf{PDC-related Core Topics}\\ \hline

Computing Essentials
       & Concurrency primitives (e.g., semaphores and monitors) \\
      & Construction methods for distributed software (e.g., cloud and mobile computing) \\ \hline
\end{tabular}
\end{table}

With reference to the above, any computer engineering or software engineering program addresses concepts on parallel and distributed software with varying levels of attainment. Students understand the intrinsic performance gains of such software, albeit they are aware that the potential gain is highly dependent on how its different parts are set to interact among each other in terms of dependencies, communications, and competitions. Per ACM/IEEE Computer Society curricular guidelines, SE and CE programs do equip their students with tools to combat the challenges of concurrency. Parallel and distributed software can indeed apply to the complex software-related ABET program criteria for CE and SE. ABET program criteria for computer engineering require that students learn to analyze and design complex software among others. Although analysis and design of application-specific algorithms represent one individual knowledge unit of computing algorithms area in computer engineering, incorporating PDC concepts described in both knowledge areas on computing and software design yields complex software, thereby meeting the corresponding ABET program criterion.

With reference to the ABET program criteria for software engineering, the curriculum must include software engineering tools appropriate for the development of complex software systems. The attainment of the specified PDC-related topics on concurrency and construction methods for distributed software as per SE2014 with the recommended cognitive skill level allows strengthening the compliance with this criterion.

In short, even though the ABET program criteria for computer and software engineering do not explicitly require PDC coverage, it is clear by looking at the curricular guidelines for both programs, it is simply not possible for program graduates in these disciplines to graduate without learning PDC. The computer engineering and software engineering programs at the authors' institutions anecdotally verify this claim.

\section{Final Remarks}
\label{FINAL}

Given the ubiquity of PDC in all aspects of modern society, it is incumbent upon contemporary computing and engineering programs to include appropriate coverage of these topics. Accordingly, parallel and distributed computing knowledge areas are emphasized in the latest ACM curricula, notably CC2020~\cite{CC2020final}'s draft competencies for PDC within CS.

Program accreditation also has a role to play in moving curricula forward.  The latest ABET's CAC criteria started requiring PDC exposure for CS programs in 2018~\cite{CACCriteria}.  These criteria already have led to systematically increasing PDC coverage, as illustrated by our survey of 20 of the top accredited CS programs and the detailed examination of how three accredited CS programs cover PDC. Two approaches to cover PDC were observed: a predominant one that uses multiple topics across various computer science courses, and a second approach that uses a dedicated PDC course.  Both approaches are viable and meet the current ABET criteria.

It is expected that PDC will continue to gain importance in computing curricula  with recent computing development and applications.  Engineering, on the other hand, has a more general approach in line with the centuries of engineering education and practice.  Thus, this paper also explored whether today's engineering graduates are also exposed to PDC concepts to be ready for careers in their disciplines. The conclusion is that ABET program accreditation has played a useful role in infusing PDC topics into CS programs around the world at a faster pace, thus leading to stronger and wider PDC coverage.

\section*{Acknowledgment}

Raj acknowledges support provided by the US National Science Foundation under Awards 1922169 and 2021287.

\balance
\bibliographystyle{ieeetr}


\section{Conclusion}
In this paper, we proposed a novel framework for complex table retrieval.
The \texttt{GTR}\xspace framework includes a
tabular graph representation strategy that
captures the cell structure dependencies,
with row nodes and column nodes for high-level feature aggregation.
\texttt{GTR}\xspace applies a tabular Graph Transformer to effectively support multi-granular feature extraction with tabular graphs as inputs.
In addition, we introduced a self-supervised pre-training task which leverages the contextual information as free-labels, so as to enhance the robustness of the tabular Graph Transformer. At last, a comprehensive set of experiments and analysis show \texttt{GTR}\xspace's state-of-the-art performance based on NLTR benchmarks, and demonstrate the capability of this framework in terms of cross-dataset generalization, handling complex table structures, and fulfilling diverse query intents.
For future work, we plan to extend the use of \texttt{GTR}\xspace to other table-related tasks, such as table summarization \cite{bao2018table,chen2020logical} and table-text grounding \cite{kim2018facilitating}.
Applying the graph-based table representation for perceptional tasks, such as cell structure recognition \cite{zheng2021global} and functional block detection \cite{sun2021hybrid}, is another meaningful direction.

\section*{Acknowledgement}

We appreciate the anonymous reviewers for their insightful comments and suggestions.
This material is based upon work sponsored by the DARPA MCS program under Contract No. N660011924033 with the United States Office Of Naval Research, and by Air Force Research Laboratory under agreement number FA8750-20-2-10002.
\subsection{Ablation Study} \label{sec:ablation}

To further help understand the contribution of each incorporated model component, we hereby conduct
several aspects of ablation studies based on WikiTables. The discussed results are in \Cref{table:ablation}.

\stitle{Table Graph Reprepresentation}
We first examine the effectiveness of the graph representation as well as the tabular Graph Transformer.
As expected, the performance drastically drops when ignoring the information in table cells and ignoring the table layouts, leading to
a relative drop of NDCG@5 by 8.77\%.
Besides, NDCG@5 decreases by relatively 5.56\% when each table unit is captured independently (i.e., removing edges).
The results indicate that both information inside each cell and dependencies among cells are important for comprehensive table understanding.
Lastly, using multi-head Graph Attention Network (GAT) \cite{velickovic2018graph} instead of Graph Transformer leads to relatively 1.46\% of drop in NDCG@5.

\stitle{Row and Column Nodes}
When removing row and column nodes from tabular graphs, the performance is lessened by 2.30\% in terms of NDCG@5, and by 4.00\% in terms of NDCG@20 relatively.
Presumably this is because Graph Transformer with cell nodes alone cannot effectively capture row-wise and column-wise information.
Thus, it is essential to use row nodes and column nodes for that level of coarse-grained information aggregation.

\stitle{Text Encoders}
We test if node initialization can benefit from a deep contextualized embedding.
Interestingly, we observe that initializing node features by encoding cell text with BERT \cite{devlin2019bert} performs worse than with FastText \cite{joulin2017bag}.
The NDCG@5 drops by 1.25\% and the NDCG@20 drops by 3.38\%, relatively.
This is understandable, since each cell content is a standalone short piece of text that does not necessarily benefit from contextualized text embedding by BERT.
On the contrary, the static embedding by FastText support with more stable semantic representation to jump-start the node features based on the short cell content.
This is in line with the observation where static embeddings outperform contextualized embeddings on lexical and phrasal tasks \cite{ethayarajh2019contextual,liu2020towards,chen2019retrofitting}.

\subsection{Case Study}\label{sec:case}
We present a case study with a representative example (\Cref{fig:case}) to illustrate how the graph representation supports with multi-granular information aggregation to fulfill the query intent. The importance of tabular graph nodes in the heat-map reflects the index frequency of node representations in max-pooling operation.

We observe when answering the query \textit{``asian countries currency''}, the first column and the seventh column of the retrieved table contribute the most. This is reasonable as both columns cover some aspects of the query. The first column is the header of rows, indicating that this table is about countries and their currencies. The seventh column is the currency of an Asian country Lebanon.
This phenomenon shows the effectiveness of global nodes in tabular graphs.
However, the tenth column, which is also about the currency of an Asian country Syria, does not attract as much attention as the seventh column does. One possible reason is that when more than one node covers similar information, the max-pooling operator may take the most informative one to leave capacity for other kinds of information. In this case, one of Lebanon and Syria is sufficient to fulfill the query intent about Asian countries.
Moreover, we observe that some cell nodes, such as the node of ``Currency'' in the first column and nodes of cells in the seventh column, also have a high frequency to be selected by max-pooling. This shows that both global nodes and local nodes can contribute to query-graph matching.
Some neighbors of the highly influential nodes mentioned above may also be frequently selected by pooling. This is likely attributed to that relevant information is propagated through the tabular graph from highly influential nodes to their neighbors.

\subsection{Generalizability Analysis}\label{sec:generalizability}

We further present several aspects of generalizability experiments, with detailed analysis on cross-dataset generalization, reactions to query intents and performance on complex tables.
In these experiments, we compare \texttt{GTR}\xspace with
the two best-performing baselines BERT4TR and TaBERT.

\stitle{Cross-dataset Evaluation}
In the first experiment, we compare NLTR methods in an inductive evaluation setting,
seeking to examine how well they can transfer knowledge to retrieve tables across datasets.
Specifically,
we train \texttt{GTR}\xspace and the two baselines on a subset of query-table pairs from WebQueryTables, and evaluate on WikiTables.
Note that the relevant tables in the two datasets are collected from different sources.
In addition,
to study the data efficiency of training the models,
we vary the size of the training set to be 1,500, 3,000, and 6,000, which are approximately half, equal and double of the size of the test set, respectively.

The results are accordingly presented in \Cref{fig:extrinsic},
which indicate that our method yields better performance than BERT4TR and TaBERT on each setting of the training data.
In particular, \texttt{GTR}\xspace exhibits better generalization performance even with half of the training data (by offering 0.6157 in terms of NDCG@20), in comparison to BERT4TR and TaBERT that are trained with full data (which achieve 0.5859 and 0.6060 in terms of NDCG@20, respectively).
We also observe that when the number of training samples decreases, the performance of the pervious state-of-the-art system BERT4TR drops more drastically,
while both TaBERT and \texttt{GTR}\xspace are relatively more stable.
Moreover,
when the training set is small (1,500),
the performance of TaBERT is close to \texttt{GTR}\xspace and is much better than BERT4TR.
We believe this is because TaBERT
has learned more adaptive table encoding than BERT by pre-training on large table corpus,
hence offering better cross-dataset generalization than BERT4TR when without sufficient fine-tuning data. However, it still drastically fall behind \texttt{GTR}\xspace.

Meanwhile, we observe noticeable performance drop by our method when pre-training is disabled, especially in cases with less training data.
This indicates the effectiveness of pre-training to improve cross-dataset generalization.
Though even without pre-training, \texttt{GTR}\xspace still consistently outperforms the two strong baselines.

\stitle{Performance by Query Intents}
In the second experiment, we show how well \texttt{GTR}\xspace and both baselines react to query intents on different granularities of content.
Following \citet{sun2019content}, we split queries from the WikiTables dataset into two main groups, i.e. \textit{general queries} and \textit{specific queries}, based on their intents.
A general query usually refers to a whole table involving several aspects of objects
while a specific query usually asks about a specific local aspect of the table in a row, a column or individual cells.
For example, \textit{``world interest rates table''} refers to a general query and \textit{``2008 Olympics gold medal winners''} is a more specific query.

\Cref{fig:intent} presents the results.
For both general and specific query intents, \texttt{GTR}\xspace significantly outperforms both BERT4TR and TaBERT.
The reason is mainly attributed to that our graph representation strategy, especially the incorporation of multi-granular node encoding,
naturally provides a multi-granular content summarization to fulfill query intents of different specificities.
Meanwhile,
the two strong baseline methods perform differently on reacting to the query intents. Specifically, TaBERT performs slightly better than BERT4TR on general queries, but being worse on specific queries.
This is most likely due to the difference in the table unit selection processes of these two methods.
Both methods select highly relevant table units according to a given query as model inputs, but TaBERT creates synthetic rows by regrouping cell content from each column.
Although this process remains the most relevant table content to queries, it may hinder the model to capture the original semantics of table units.
We also observe that our method benefits much from pre-training to deal with general queries. We believe this benefits from contextual information (e.g. captions) in the pre-training task of graph-context matching (\Cref{sec:pretrain}), where the contextual information serves as general descriptions of tables.

\stitle{Performance on Complex Tables}
In the third experiment, we evaluate how different methods are capable of handling complex tables.
To do so, we preserve only 1,886 tables with nested structures in cross-validation.
Results in \Cref{fig:complex} show that \texttt{GTR}\xspace, with or without pre-training, notably outperforms both TaBERT and BERT4TR under this setting.
It verifies that our graph representation strategy is better at capturing complex table layouts than Transformer language model based methods,
as our method captures the essential structural layout information rather than flattening table cells into a sequence.
Interestingly, we observe that TaBERT performs better than BERT4TR on retrieving complex tables, which is just the opposite when retrieving from the whole table corpus (\Cref{table:wikitables}
.
Meanwhile, \texttt{GTR}\xspace also performs much better with pre-training,
indicating pre-training task to be beneficial to complex table representation.

According to the experiments, our method is capable of effectively transferring knowledge cross datasets. In addition, the graph representation strategy allows for capturing multi-granular information to fulfill both general and specific intents.

\subsection{Main Results} \label{sec:results}

\begin{table*}[t]
\centering
\caption{
Ablation study on framework components.
\textit{Removing Tabular Graph} removes the entire query-graph matching module. \textit{Removing Edges} keeps nodes but removes all edges in the tabular graph. \textit{Mult-head GAT} uses a multi-head Graph Attention Network as the encoder. \textit{Removing Row and Col Nodes} removes row and column nodes. \textit{Node Initialization with BERT} replaces FastText with BERT as the cell text encoder. $\downarrow$ marks a significant drop of a metric by at least $4\%$ relatively.
}
\begin{tabular}{l|lllll}
\toprule
 Setting & NDCG@5 & NDCG@10 & NDCG@15 & NDCG@20 & MAP   \\
 \midrule
Default & 0.6554 & 0.6747 & 0.6978 & 0.7211 & 0.6665 \\
\midrule
- Removing Tabular Graph & 0.5979 $\downarrow$ & 0.6118 $\downarrow$ & 0.6395 $\downarrow$ & 0.6606 $\downarrow$ & 0.6231 $\downarrow$ \\
- Removing Edges & 0.6190 $\downarrow$ & 0.6438 $\downarrow$ & 0.6669 $\downarrow$ & 0.6956 & 0.6513 \\
- Multi-head GAT & 0.6458 & 0.6553 & 0.6728 & 0.6977 & 0.6546 \\ \midrule
- Removing Row and Col Nodes & 0.6403 & 0.6566 & 0.6704 & 0.6922 $\downarrow$ & 0.6494 \\ \midrule
- Node Initialization with BERT  & 0.6472 & 0.6417 $\downarrow$ & 0.6652 $\downarrow$ & 0.6967 & 0.6472 \\
\bottomrule
\end{tabular}
\label{table:ablation}
\end{table*}

The main results presented here are under the intrinsic evaluation protocol following the design of the two NLTR benchmarks.

As reported in
\Cref{table:wikitables} and \Cref{table:webquerytables},
among the baseline methods, the pre-trained Transformer language model based BERT4TR demonstrates state-of-the-art performance over other baselines.
The reason is that that pre-trained language models more comprehensively capture the semantic information of table cell content and context information, in comparison to a number of other baselines based on explicit features or static embeddings.
In particular, though TaBERT follows is similar to BERT4TR, it offers a less performance.
We hypothesize that since TaBERT is designed for semantic parsing tasks where the focus is to capture column relations, it does not necessarily support well summarizing table content and inferring the query-table affinity.

We observe that our method, even without pre-training, outperforms BERT4TR and TaBERT with at least relative improvements of 8.29\% in terms of NDCG@5, 9.34\% in terms of NDCG@10, 8.17\% in terms of NDCG@15,  7.80\% in terms of NDCG@20 and 5.36\% in terms of MAP, on the WikiTables dataset.
It is noteworthy that, both BERT4TR and TaBERT are Transformer-based architectures that flatten table cells to sequences.
This strategy of representation necessarily discards the dependencies between subtable content that are modeled in the table layouts.
The graph representation and coupled tabular Graph Transformer in our framework preserve the original structures of table content, and encapsulate features of table cells in different granularities.
The experimental results verify our hypothesis that structure-aware representations and multi-granular information of tables are conducive to general purpose NLTR.

Pre-training the query-graph matching module further leads to at least a relative improvement of 1.78\% in terms of NDCG@5, and that of 2.91\% in terms of MAP.
This is attributed to that the query-graph matching module acquires more robust characteristics of tables during the pre-training process,
hence particularly benefits the training that does not involve lots of data.

The evaluation on the WebQueryTable dataset supports the same conclusion.
\texttt{GTR}\xspace outperforms BERT4TR with a relative increase of MAP by 3.73\% without pre-training and 4.97\% with pre-training,
with more improvement in comparison to other baselines.
The two datasets have different annotation strategies and sources of relevant query-table pairs.
These results indicate that \texttt{GTR}\xspace adapts well to different scenarios of NLTR.

\subsection{Experimental Setup}\label{sec:setup}

\begin{table*}[t]
\centering
\caption{Retrieval performance on WikiTables. The best performing method in each column is boldfaced, and the second best method is underscored. Baselines are organized into (1) unsupervised, (2) feature engineering and (3) end-to-end groups.}
\begin{tabular}{l|ccccc}
\toprule
Method & NDCG@5 & NDCG@10 & NDCG@15 & NDCG@20 & MAP   \\ \midrule
BM25 & 0.3196 & 0.3377 & 0.3732 & 0.4045 & 0.4260 \\ \midrule
WebTable & 0.2980 & 0.3150 & 0.3486 & 0.3922 & -\\
SDR & 0.4573 & 0.4841 & 0.5195 & 0.5534 & -\\
MDR & 0.5021 & 0.5116 & 0.5451 & 0.5761 & -\\
Tab-Lasso & 0.5161 & 0.5018 & 0.5330 & 0.5481 & -\\
LTR & 0.5910 & 0.5712 & 0.5858 & 0.6041 & 0.5615  \\ \midrule
TaBERT & 0.5926 & 0.6108 & 0.6451 & 0.6668 & 0.6326 \\
BERT4TR & 0.6052 & 0.6171 & 0.6386 & 0.6689 & 0.6191 \\ \midrule
\texttt{GTR}\xspace (w/o pre-training) & \underline{0.6554} & \underline{0.6747} & \underline{0.6978} & \underline{0.7211} & \underline{0.6665} \\
\texttt{GTR}\xspace  & \textbf{0.6671} & \textbf{0.6856} & \textbf{0.7065} & \textbf{0.7272} & \textbf{0.6859} \\
\bottomrule
\end{tabular}
\label{table:wikitables}
\vspace{-1em}
\end{table*}

\begin{table}[t]
\centering
\caption{Retrieval performance on WebQueryTable.
P@1 is not reported by the BERT4TR paper.}
\begin{tabular}{l|cc}
\toprule
Method & P@1 & MAP   \\ \midrule
BM25 & 0.4712 & 0.5823 \\ \midrule
MDF & 0.4779 & 0.6102 \\ \midrule
MNN & 0.4902 & 0.6194 \\
TaBERT & 0.5067 & 0.6338 \\
BERT4TR & - & 0.7104 \\ \midrule
\texttt{GTR}\xspace (w/o pre-training) & \underline{0.6257} & \underline{0.7369}\\
\texttt{GTR}\xspace & \textbf{0.6358} & \textbf{0.7457}\\
\bottomrule
\end{tabular}
\label{table:webquerytables}
\vspace{-1em}
\end{table}

\stitle{Datasets}
We conduct experiments on two benchmark datasets, i.e. WikiTables \cite{zhang2018ad} and WebQueryTable \cite{sun2019content}. The relevant query-table pairs of these two datasets are collected from different sources. More details and statistics of the datasets are described as follows:

\begin{itemize}[leftmargin=*]

\item \textbf{WikiTables:}
WikiTables is a widely-used dataset for the NLTR task. It contains 60 queries
that are contributed by two previous studies \cite{cafarella2009data, venetis2011recovering}.
3,120 candidate tables were extracted from Wikipedia.
All candidate tables were
labeled by annotators with one of three relevance scores: 0 (irrelevant), 1 (relevant), and 2 (highly relevant). Each table is associated with contextual information including a caption, Wikipedia's page title and section title.
We analyzed the cell adjacency of these tables and discovered that 1,886 of them came with nested layout structures involving merged cells.
Following previous works \cite{zhang2018ad, chen2020table}, we
run 5-fold cross-validation on this dataset.

\item \textbf{WebQueryTable:}
The WebQueryTable dataset contains 21,113 queries collected from search logs of a commercial search engine and 273,816 tables. For each query, one relevant table was obtained from the top ranked Web page of the same search engine after manual evaluation.
Captions of tables are also given in this dataset as contextual information. We use the originally released training, validation and test set splits \cite{sun2019content} for evaluation.
\end{itemize}

\stitle{Baselines}
We compare our framework \texttt{GTR}\xspace with the following 10 strong baseline methods\footnote{We did not compare with STR \cite{zhang2018ad} which used addtional entity and categorical information. Also, MTR \cite{shraga2020web} was reported in a different experimental setting, but its implementation had not been released by the time this paper was written.}.

\begin{itemize}[leftmargin=*]

\item \textbf{BM25 \cite{robertson1995okapi}}:
Okapi BM25 is an unsupervised method using token-matching with TF-IDF \cite{ramos2003using} weights as the scoring function.

\item \textbf{WebTable \cite{cafarella2008webtables}}:
WebTable is a method based on linear regression using hand-crafted features.

\item \textbf{SDR \cite{cafarella2009data}}:
Single-field Document Ranking (SDR) treats a table as a regular document, and uses a symmetric conditional probability model with Dirichlet smoothing to capture query-table relevance.

\item \textbf{MDR \cite{pimplikar2012answering}}: Multi-field Document Ranking (MDR) extends SDR by treating each table as multiple separated fields of text.
Each field corresponds to page titles, table section titles, table captions, table body, or table headings, respectively.
MDR also uses coordinate ascent algorithm \cite{wright2015coordinate} to learn the aggregation weights.

\item \textbf{Tab-Lasso \cite{bhagavatula2013methods}}:
Tab-Lasso is a Lasso \cite{tibshirani1996regression} model with coordinate ascent, taking well-designed hand-crafted features as input.

\item \textbf{LTR \cite{zhang2018ad}}:
Lexical Table Retrieval (LTR) is a strong non-neural baseline,
which employs point-wise regression using Random Forest \cite{ho1995random} with features from WebTable \cite{cafarella2008webtables} and Tab-Lasso \cite{bhagavatula2013methods}.

\item \textbf{MDF \cite{sun2019content}}:
Matching with Designed Features (MDF) matches queries and tables based on lexical similarity using IDF scores, phrasal similarity using phrase dictionary tables \cite{koehn2003statistical}, and sentential  similarity using the CDSSM \cite{shen2014latent} model, respectively.

\item \textbf{MNN \cite{sun2019content}}:
Matching with Neural Networks (MNN) is a method that uses bi-directional gated recurrent unit (GRU) \cite{cho2014learning} to encode queries and captions, and applies query-specific attention mechanisms to aggregate cell embeddings to represent table units.

\item \textbf{BERT4TR \cite{chen2020table}}:
BERT for Table Retrieval (BERT4TR) is the previous state-of-the-art method that applies the pre-trained language model BERT \cite{devlin2019bert} to encode flattened tables.
An embedding-based selection process is first utilized to select the most relevant rows from tables with respect to queries.
Then the query, contextual information of a table and selected tabular content is flattened as a sequence and encoded by BERT, on top of which an MLP is stacked to compute the relevance score.

\item \textbf{TaBERT \cite{yin2020tabert}}:
TaBERT is a
more recently released language model that is pre-trained on a large corpus of 26 million tables and their English contexts. It has been previously applied to semantic parsing on tables and offered state-of-the-art performance.
We apply this strong table representation learning method for NLTR.
Similar to BERT4TR, we also stack an MLP scorer to calculate the query-table relevance scores.

\end{itemize}

\begin{figure*}[t]
\subfigure[Results of cross-dataset evaluation.]{
\includegraphics[scale=0.37]{figures/extrinsic.png}
\label{fig:extrinsic}
}
\subfigure[Results by query intents.]{
\includegraphics[scale=0.37]{figures/intent.png}
\label{fig:intent}
}
\subfigure[Results on complex tables.]{
\includegraphics[scale=0.37]{figures/complex.png}
\label{fig:complex}
}
\vspace{-1em}
\caption{Generalizability analysis results.}
\vspace{-1em}
\end{figure*}

\noindent
For WebTable, SDR, MDR, Tab-Lasso and LTR, we use the implementation from \citet{zhang2018ad}
\footnote{Some baseline results in \Cref{table:wikitables} may be different from those reported in previous works due to different setups of cross-validation.}.
The results for BM25, MDF, MNN and BERT4TR on WebQueryTable dataset are obtained from their original papers, where experiments are conducted using the same data split.
For BERT4TR on WikiTables dataset and TaBERT on both datasets, we use the original implementation, configuration and preprocessing steps released by the authors.

\stitle{Evaluation Metrics}
Considering the different annotation strategies of the two datasets, we adopt different groups of metrics to evaluate the retrieval performance on each dataset, as to be consistent with prior studies.
On WikiTables, following previous works \cite{zhang2018ad, chen2020table}, we report Mean Average Precision (MAP) and Normalized Discounted Cumulative Gain (NDCG@$k$) with cut-off points $k=\{5,10,15,20\}$.
On WebQueryTable, we report MAP and Precision at 1 (P@1) following \citet{sun2019content}.
Specifically, MAP and NDCG metrics are calculated using the TREC evaluation tool\footnote{\url{https://github.com/usnistgov/trec_eval}}.

\stitle{Implementation Details}
For the default version of \texttt{GTR}\xspace, we use BERT as the query-context matching module and FastText \cite{joulin2017bag} as the text encoder for query-graph matching module (see \Cref{sec:ablation} for ablation on text encoders).
In query-graph matching module, we use four layers of Graph Transformer ($L=4$) with four self-attention heads ($H=4$).
The dimensionality of hidden states is set to 300.
In query-context matching module, multiple text sequences from the query and context are concatenated and fed to BERT. Following \citet{devlin2019bert}, we add a \texttt{[CLS]} token at the beginning of the input sequence, and separate query and context with a \texttt{[SEP]} token. Different segment embeddings are assigned to distinguish query from context. We use the final output of the first token \texttt{[CLS]} as the hidden state of query-context matching.
As described in \Cref{sec:matching}, the learning objective is set to be MSE on WikiTables where multiple relevant tables coexist for each query, and that is set to a NLL loss on WebQueryTable where each query has only one relevant table.

Both pre-training and the main training process use an Adam optimizer with learning rate set as $0.0001$.
Pre-training of the query-graph matching module uses tables from both WikiTables and WebQueryTable datasets.
It is conducted for 20 epochs with a batch size of 16, so as to fit into one RTX 2080 GPU.
The main training process on both datasets takes 5 epochs with a linear learning rate scheduler with warmup steps.
The training configurations on both datasets are slightly different, as being limited by the GPU memory.
On the WikiTables dataset, we use batch size of 16 and warmup steps of 100.
On the WebQueryTable dataset, we use batch size of 4 and warmup steps of 1000.
Trainable parameters other than text encoders are initialized using the Xavier initializer \cite{glorot2010understanding}.
Dropout rate of 0.1 is applied to each Graph Transformer layer and before the final MLP.
The negative slope of LeakyReLU is set as 0.2.
We use Pytorch \cite{paszke2019pytorch} and DGL \cite{wang2019dgl} to implement our framework.

\section{Experiment}

In this section,
we conduct experiments based on two benchmark datasets (\Cref{sec:setup}) and compare the performance of \texttt{GTR}\xspace against a series of recent baselines (\Cref{sec:results}).
We also provide quantitative analysis on the generalizability of our method (\Cref{sec:generalizability}),
and conduct detailed ablation studies (\Cref{sec:ablation})
and case studies (\Cref{sec:case}) to help understand the contribution of different model components.

\input{sections/experiment/setup}
\input{sections/experiment/main_result}
\input{sections/experiment/generalizability}
\input{sections/experiment/ablation}
\input{sections/experiment/case}

\section{Introduction}

Web tables are rich sources of semi-structured knowledge that benefit a wide range of applications.
For example, Wikipedia contains millions of high-quality tables that support various knowledge-driven tasks, such as table-based question answering \cite{pasupat2015compositional}, fact verification \cite{chen2019tabfact} and table-to-text generation \cite{lebret2016neural}.
Additionally, tables are ubiquitous in scientific literature and financial reports and have inspired research efforts on table profiling \cite{liu2007tableseer}, table-text grounding \cite{kim2018facilitating}, tabular semantic parsing \cite{fang2012table}, etc.

As an important component of Web information, tables are presented as direct results to Web queries in search engines \cite{balakrishnan2015applying}. Traditional formal methods for information retrieval from databases (e.g. SQL, QBE \cite{zloof1975query} and QUEL \cite{stonebraker1976design}) and
formal query generation methods (e.g. text-to-SQL \cite{wang2015building, xu2017sqlnet}) do not provide a flexible way to support
information retrieval from Web tables with varied structures.
Therefore, the task of \textit{natural language table retrieval} (NLTR) \cite{zhang2018ad} has been proposed, offering more flexibility for directly searching semantically relevant tables based on search queries described in natural language.
Moreover, NLTR is a key building block for tasks that require synthesizing knowledge from tables, such as table-based reading comprehension \cite{wang2018neural}, open fact verification \cite{schlichtkrull2020joint}, and open domain question answering \cite{chen2021open, chen2020hybridqa}. While Web tables are beneficial to many downstream tasks, a key issue in those tasks in real-world scenarios lies in the difficulty of efficiently collecting relevant tables from a large table corpus. NLTR can then be used to identify candidate tables for those tasks.

\begin{figure*}[t]
\vspace{-0.5em}
\centering
\subfigure[Relational table]{
\includegraphics[width=0.2\textwidth]{figures/t1.png}
\label{fig:t1}
}
\subfigure[Entity table]{
\includegraphics[width=0.21\textwidth]{figures/t2.png}
\label{fig:t2}
}
\subfigure[Matrix table]{
\includegraphics[width=0.22\textwidth]{figures/t3.png}
\label{fig:t3}
}
\subfigure[Nested table]{
\includegraphics[width=0.28\textwidth]{figures/t4.png}
\label{fig:t4}
}
\vspace{-1.5em}
\caption{Example snippets of tables with diverse layout structures.}
\label{fig:layout}
\vspace{-0.5em}
\end{figure*}

A common challenge of NLTR lies in the fact that tables consist of both structured table cells and unstructured contextual information (e.g. captions).
A simple method to deal with both types of information is treating tables as plain text \cite{cafarella2008webtables, cafarella2009data, pimplikar2012answering}. In this way, the problem is reduced to document retrieval, but the characteristics of different types of information, especially the semantic dependency among table cells is ignored.
Text in each cell of a table contains limited knowledge and are sometimes meaningless without dependencies.
For example, in \Cref{fig:t3}, numerical cells do not provide meaningful knowledge unless aligned with attributes in row and column headers.
As an attempt to capture the information in different substructures of a table, \citet{chen2020table} designed an embedding-based feature selection technique to select from each table the rows, columns and cells that are relevant to a query. Then they applied the pre-trained language model BERT \cite{devlin2019bert} to encode selected table content.
\citet{shraga2020web} treated different types of information as multimodal objects and used recurrent neural networks (RNN) or convolutional neural networks (CNN) to encode each of them.
\citet{sun2019content} utilized attention mechanism to select cell embeddings over each row and each column.
The approaches in prior studies have offered decent performance in intrinsic evaluation settings \cite{zhang2018ad, sun2019content, chen2020table}. However, they are still quite distant from a generalizable solution to the NLTR problem.

To effectively address the NLTR problem, a learning-based system needs to tackle three aspects of generalization issues, which are however overlooked by prior approaches.
First, as shown in \Cref{fig:layout}, table cells are organized in diverse layouts to express the complex dependencies between cells.
For example, we find that around 63.8\% of WikiTables \cite{zhang2018ad} come with nested structures of merged cells.
Failing to consider these complex layout structures prevents the extraction and synthesizing of semantic knowledge from these tables.
Second, natural language queries may have varied intents, referring to various granularities of content stored in different subunits of a table, such as cells, rows and columns.
For example,
the table in Figure 2(a) is relevant to queries for ``taxable wages'' at table-level, ``dependent allowance'' at row-level, and ``yearly aggregates'' at column-level.
\citet{sun2019content} analyzed a subset of the WebQueryTables dataset and found that about 24.5\% queries are asking for information in specific subtable units while about 69.5\% are asking for a whole table.
Third, tables and queries from different datasets can possess dissimilar content, therefore requiring a generally applicable retrieval model to be adaptive to different datasets.
Some work \cite{chen2020table, sun2019content}
collects datasets from different sources and perform intrinsic evaluation on each of them.
Nonetheless, prior methods fall short under cross-dataset evaluation \cite{chen2020empirical}, i.e. training on one dataset and testing on another dataset.

To this end, this paper proposes a novel table retrieval framework, namely \texttt{\underline{G}}raph-based \texttt{\underline{T}}able \texttt{\underline{R}}etrieval (\texttt{GTR}\xspace~\includegraphics[height=0.7em]{figures/gtr-nismo.png}), to tackle the generalization issues (\Cref{sec:method}).
\texttt{GTR}\xspace leverages state-of-the-art graph representation learning techniques to capture both content and layout structures of complex tables.
Specifically, \texttt{GTR}\xspace
incorporates a process to convert layout structures to \emph{tabular graphs}, with cell nodes, row nodes, and column nodes to capture tabular information in different subunits.
A variant of Graph Transformer \cite{koncel2019text} is then applied for automatic feature extraction from tabular content (\Cref{sec:tabular_graph}), providing a structure-aware and multi-granular semantic representation for each unit.
Then given a query, the framework uses two matching modules to measure the relevance
scores based on both cells and contextual information of tables (\Cref{sec:matching}).
To further improve the adaptivity of \texttt{GTR}\xspace, we design a pre-training process to enhance the robustness of the query-graph matching module  (\Cref{sec:pretrain}).
Experimental results on two benchmark datasets show that our method achieves significant improvements over prior state-of-the-art methods, even without pre-training (\Cref{sec:results}).
In particular, our method outperforms the best-performing baseline on both datasets by 8.27\% and 4.97\% in terms of MAP.
Further experimentation (\Cref{sec:generalizability})
also demonstrates that the \texttt{GTR}\xspace framework exhibits promising cross-dataset generalization performance, and shows stronger ability to handle complex tables and diverse query intents than existing methods.

In summary, this paper makes three major contributions:
(1) a novel graph representation strategy captures complex layouts of tables and preserves structural dependencies between table units;
(2) a
query-graph matching process with a pre-trained Graph Transformer
provides robust characterization of tables and supports multi-granular feature extraction for varied query intents;
(3)
a comprehensive set of experimentation shows the superior performance of the proposed method based on NLTR benchmarks and verifies the effectiveness in terms of cross-dataset generalization, complex table representation and query intent adaptation.

\begin{figure*}[t]
\centering
\subfigure
{
\includegraphics[width=0.55\textwidth]{figures/example_table.png}
\label{fig:table_example}
}
\hspace{5pt}
\subfigure
{
\includegraphics[width=0.25\textwidth]{figures/example_graph.png}
\label{fig:graph_example}
}
\vspace{-1.5em}
\caption{Multi-granular query intents and the tabular graph construction process for a table with complex layout.}
\label{fig:table_graph}
\vspace{-0.5em}
\end{figure*}

\section{Method} \label{sec:method}

\begin{figure*}[htbp]
\centering
\includegraphics[width=0.81\textwidth]{figures/framework.png}
\vspace{-1em}
\caption{The overall architecture of the \texttt{GTR}\xspace framework. \textit{Vector Combination} thereof refers to operations in \Cref{sec:matching}. Numbered markers correspond to the components described in Method Overview (\Cref{sec:preliminary}).}\label{fig:framework}
\vspace{-1em}
\end{figure*}

In this section, we first provide a formal definition of the NLTR task (\Cref{sec:preliminary}), and then introduce the architectures of the main components in our framework (\Cref{sec:matching,sec:tabular_graph}).
This is followed by the technical details of training, pre-training (\Cref{sec:pretrain}) and inference (\Cref{sec:inference}) processes.

\subsection{Preliminaries} \label{sec:preliminary}

\stitle{Task Definition}
Given a natural language search query $q \in \mathcal{Q}$ and a set of tables $\mathcal{T}_q = \{ T_1, T_2, ..., T_p \}$, the goal of the NLTR task is to rank tables from $\mathcal{T}_q$ according to
how likely $q$ can be satisfied by the information in each table.
The main body of a table contains two types of content, i.e. \emph{table cells} and \emph{contextual information}.
Table cells
can contain both header cells that describe attributes or names, and basic data cells\footnote{Sometimes table titles and footnotes also appear as (merged) cells.}~\cite{zhang2020graph}.
Different from previous works, we do not make the assumption that
these table cells necessarily form a matrix-like layout \cite{chen2020table, shraga2020web}.
Meanwhile, tables are associated with \textit{contextual information} (e.g. captions and footnotes), which have also been used as side information to characterize a table in previous works \cite{chen2020table, shraga2020web, zhang2020graph}.
Following the aforementioned works, our work also leverages these two components, i.e. table cells and contextual information, to characterize a table. ~\Cref{fig:table_example} shows an example. The caption \textit{``Taxing wages in the United States''} is the contextual information and the main content is presented in several table cells.

\stitle{Method Overview}
The overall architecture of \texttt{GTR}\xspace is given in \Cref{fig:framework}.
Specifically, the framework consists of three model components:
(1) a query-graph matching module captures the cells of a table with a multi-granular graph representation (\Cref{sec:tabular_graph}), and
estimates how relevant the cell content is based on such a representation
(\Cref{sec:matching});
(2) a query-context matching module assesses the relevance of a table to a query based on the contextual information associated with the table (\Cref{sec:matching});
and
(3) a ranking module that combines the outputs of two aforementioned matching modules and calculates the relevance score for each candidate query-table pair (\Cref{sec:matching}).
To further explore the potential of our framework, especially the generalizability
of the
query-graph matching module, we also incorporate a novel pre-training process (\Cref{sec:pretrain}).

\subsection{Graph Representation of Tables} \label{sec:tabular_graph}

\stitle{Tabular Graph Construction}
To effectively characterize a table with arbitrary layout, the first step is to transform the table into a multi-granular graph representation.
In detail,
a table $T$ can be split into a set of units.
Each unit refers to an individual cell, a row or a column.
Units are interconnected in different ways depending on the table layout, and each unit can contain different types of information.
This characteristic of tables is similar to that of graphs. In particular, each table unit can be treated as a node $v_i \in V$ in a graph $G = (V, E)$, and the connection between two table units becomes an edge $e=(v_i, v_j)\in E$ between their corresponding nodes. In this paper, we consider two kinds of connections between table units: between adjacent cells; and between a unit and its subunit, such as a row and a cell in this row.

\Cref{fig:table_graph} shows an example of a table and its tabular graph. Suppose we have a table
about taxing wages. The table has 11 cells in total where four cells are merged cells.
In the corresponding tabular graph, each cell has an associated node.
In addition, we have global nodes that capture the information of each row and column. Between each pair of adjacent cell nodes, we add a bidirectional edge.
Every global node has a unidirectional edge sourced from each constituent cell node.
These edges allow global nodes to aggregate information from the respective cells in the row or column.

\stitle{Tabular Graph Transformer}
Once a table is converted to a tabular graph, we use a variant of Graph Transformer \cite{koncel2019text} to characterize both cell content and layout structures.
In detail, this process starts with initial representations $\mathbf{V}^0 = \{\mathbf{v}_i^0\}$ of node features,
which are obtained using a pre-trained text encoder to encode the table unit content referring to each node\footnote{For global nodes, we average text embeddings of constituent cells as node features.}.
We compare different text encoders in \Cref{sec:ablation}.
These encodings along with the tabular graph introduced in the previous section are used as inputs to a Graph Transformer.
Every $l$-th layer of the Graph Transformer thereof incorporates a multi-head self-attention layer with residual connection, a feedforward neural network layer ($FFNN$) and layer normalization ($LayerNorm$) \cite{ba2016layer}:
$$ \mathbf{v}_i^{l+1} = LayerNorm(FFNN(\sigma( \mathbf{W}^l_g \mathbf{v}_i^{l} + \mathop{\bigg|\bigg|} \limits_{h=1}^{H} \sum_{j \in \mathcal{N}_i} \alpha^{lh}_{ij} \mathbf{W}^{lh}_g \mathbf{v}_j^{l} ))) ,$$
where
$\sigma$ denotes the Leaky Rectified Linear Unit (LeakyReLU) \cite{maas2013rectifier},
$\mathbf{W}^l_g$ is a trainable weight matrix
that transforms $\mathbf{v}_i^{l}$ to the same size of the output of multi-head self-attention layer,
$\big|\big|$ denotes the concatenation operation over $H$ attention heads,
$\mathcal{N}_i$ denotes the neighborhood of node $v_i$ in $G$,
and
$\alpha^{lh}_{ij}$ is the attention\footnote{We use additive attention mechanism \cite{bahdanau2015neural}. Other mechanisms, such as dot-product attention \cite{luong2015effective}, can also be applied, though we observe similar performance.} score of node $v_j$ to node $v_i$ in the $h$-th head of the $l$-th layer:
$$ \alpha^{lh}_{ij} = \frac{exp(a^{lh}_{ij})}{\sum_{j' \in \mathcal{N}_i} exp(a^{lh}_{ij'})} ,$$
$$ a^{lh}_{ij} = \sigma(\mathbf{w}_{lh}^T [\mathbf{W}^{lh}_a \mathbf{v}_i^{l} \ \big|\big|\  \mathbf{W}^{lh}_a \mathbf{v}_j^{l}]) .$$
We stack $L$ layers of Graph Transformer to allow tabular deatures to pass through the graph structure.
Note that both local neighborhood information of cell nodes and global information of row and column nodes are captured through message passing.

\subsection{Query-Table Matching}\label{sec:matching}

\stitle{Query-Graph Matching}
After obtaining the embedding representation of tabular content, we then need to match the tabular graph with the query. This process is completed by the query-graph matching module.
Given representations of individual nodes in the graph, we first apply a linear transformation and layer normalization to these representations:
$$ \mathbf{v}_i = LayerNorm(\mathbf{W}_{1} \mathbf{v}_i^{L} + b_{1}).$$
Meanwhile, a sentence encoder is used to encode the query (implementation details see \Cref{sec:setup}).
Each encoded node representation $\mathbf{v}_i\in\mathbf{V}$ and the query representation $\mathbf{q}$ are
concatenated together with their
element-wise subtraction and Hadamard product:
$$\mathbf{\hat h}_{i} = [\mathbf{v}_i \ \big|\big|\  \mathbf{q} \ \big|\big|\  \mathbf{v}_i - \mathbf{q} \ \big|\big|\  \mathbf{v}_i  \circ \mathbf{q}]$$
Note that this is shown to be a comprehensive way to model
embedding interactions in previous works \cite{wang2020joint,zhou2020mutation}.
Then another non-linear transformation with tanh\footnote{The sequence output of BERT is activated by tanh function, which keeps the outputs of query-context matching and query-graph matching modules at the same scale.} activation function is applied
to produce hidden representations:
$$\mathbf{h}_{i} = Tanh(\mathbf{W}_{2} \mathbf{\hat h}_{i} + b_{2}) .$$
Finally, we aggregate the hidden representations of all nodes with a max-pooling operation, where $|V|$ is the number of nodes in $G$:
$$\mathbf{h}_{qd} = \mathop{MaxPooling} (\mathbf{h}_{1}, \mathbf{h}_{2}, ..., \mathbf{h}_{|V|}).$$

\noindent
Note that the design of this module is motivated by the need for fulfilling varied queried intents in NLTR.
The representations of cell, row and column nodes encoded by Graph Transformer naturally summarize on various subunits of the table as potential references for different queries. The pooling operator over nodes is for selecting summarized content that is most relevant to a query.

\stitle{Query-Context Matching}
Contextual information associated with tables can provide side information indicating the content of tables.
To capture such side information $\mathbf{h}_{qc}$, we use a query-context matching module.
Specifically, query-context matching can be seen as short-short or long-short text matching regarding to the length of context.
Successful text matching models, such as BERT, can be used as the backbone of this module.

\stitle{Learning Objective}
The final query-table matching representation
$ \mathbf{h}_{qt} = [ \mathbf{h}_{qd} \ \big|\big|\  \mathbf{h}_{qc} ] $
is then fed to a multi-layer perceptron (MLP) to calculate the relevance score $s_k$.
Recall that the goal of the NLTR task is to rank a collection of tables $\mathcal{T}_q = \{ T_1, T_2, ..., T_p \}$ according to their relevance scores to query $q \in \mathcal{Q}$.
Since we have the relevance score $s_k$ for each table $T_k$, any ranking objectives can be used here.
Following \citet{chen2020table}, the default setting approximates point-wise ranking with a mean square error (MSE) loss:
$$ MSE = \frac{1}{|\mathcal{Q}|} \sum_{q \in \mathcal{Q}}  \frac{1}{|\mathcal{T}_q|} \sum_{k=1}^{|\mathcal{T}_q|} (s_k - y_k)^2 , $$
where $y_k$ is the gold label (relevance score) of table $t_k$.
Specifically, in the scenario where each query has only one relevant table, using the negative loglikelihood objective can achieve better performance \cite{sun2019content}. Following \citet{sun2019content}, we use negative loglikelihood (NLL) as the loss function for this specific situation:
$$ NLL = - \frac{1}{|\mathcal{Q}|} \sum_{q \in \mathcal{Q}} \log(\frac{\exp(s_{\hat k})}{\sum_{k=1}^{|\mathcal{T}_q|} \exp(s_{k})}) , $$
where $\hat k$ is the index of the only relevant table to each query.

\subsection{Pre-training}\label{sec:pretrain}
In order to
support robust characterization of tables, we design a self-supervised pre-training task, following the principles suggested by \citet{chang2019pre}:
(1) the pre-training task should capture self-supervision signals that are relevant to the downstream task, so that the pre-trained model can acquire essential characteristics for solving the downstream task;
and (2) the pre-training task should be cost-efficient in terms of pre-training data, ideally relying on free or self-generated labels.
Considering that a query and the contextual information of a relevant table contain semantically related information, we use the contextual information as free-labels during pre-training.

\stitle{Graph-Context Matching}
Specifically, we reuse the architecture of the query-graph matching module. Different from the original query-graph matching process, the pre-training process treats the contextual information of tables as queries and performs \emph{graph-context matching}.
During pre-training, for each table $T$ with the contextual information $c$, we randomly select the contextual information $c^\prime$ of another table.
We refer $c$ as a positive context, and $c^\prime$ as a negative context. The ``context'' here provides the same functionality as the ``query'' in \Cref{sec:matching}.
The objective of pre-training is to make $T$ more relevant to $c$ than $c^\prime$. Suppose the relevance scores from the query-graph matching module for $c$ and $c^\prime$, are $s$ and $s^\prime$, we also apply MSE as the loss function such that the ground-truth scores for $c$ and $c^\prime$ are $1$ and $0$, respectively.

\subsection{Inference}\label{sec:inference}
During inference, \texttt{GTR}\xspace retrieves tables based on both the table cells and contextual information.
\Cref{fig:framework} depicts the whole pipeline.
Given a query, for each candidate table that has been converted to its tabular graph,
both query-graph matching and query-context matching modules yield the combined representation of the query and corresponding information of the table.
As described above, the query-graph matching module has performed a pooling operation to filter the relevant information in the tabular graph.
Then, representations from both modules are further combined for an estimation of relevance score $s_k = MLP(\mathbf{h}_{qt})$.
For each query, we sort all candidate tables directly by the estimated relevance scores.

\section{Related Work}

We review two relevant research topics. Both topics have a large body of work, for which we provide a selected summary.

\subsection{Natural Language Table Retrieval}

Earlier approaches for NLTR \cite{liu2007tablerank, cafarella2009data, pimplikar2012answering} treated tabular data as plain text and used BM25-style \cite{robertson1995okapi} methods to retrieve tables in the same way as document retrieval.
Following this line, later work attempted to improve via better feature engineering, which involved handcrafted statistical and semantic features \cite{cafarella2008webtables, bhagavatula2013methods}, or utilized lexical embeddings \cite{zhang2018ad, zhang2019table2vec}.
These studies provided feasible solutions to NLTR. However, the extracted features used in these approaches have limited coverage on queries and tabular content, as they focused on specific facets.
Moreover, some strong features (e.g. entities and categorical features \cite{zhang2018ad}) were only available in specific scenarios, limiting their generalizability.

Recent work focused on neural network approaches \cite{sun2019content, chen2020table, shraga2020web, zhang2020graph}.
\citet{sun2019content} proposed query-specific attention mechanisms to aggregate table cell embeddings, which provided a flexible way to induce the relevance between a query and different parts of a table with softmax classifiers.
Through this direction,
\citet{chen2020table} designed an embedding-based feature selection technique to select most relevant content from cells, rows and columns of each table, where BERT \cite{devlin2019bert} was used to encode the concatenated text sequence of selected table content.
\citet{chen2020table} also observed that combining neural network methods and feature-based methods achieved further improvements.
\citet{shraga2020web} treated different facets of a table, including descriptions, schemas, rows and columns as different data modalities, and incorporated a multi-channel neural network to capture all modalities to be retrieved. The network was trained with both query-independent and query-dependent objectives.
\citet{zhang2020graph} constructed a graph for the query, and headers, captions and cells of a table, and incorporated a graph convolutional network (GCN) \cite{kipf2017semi} based classifier to predict the query-content relevance scores.
In addition, there have been research efforts on cascade re-ranking based on the results of single \cite{shraga2020projection} or multiple \cite{shraga2020ad} table retrieval methods.

The proposed table retrieval approach in this paper is connected to neural network approaches. The main difference lies in two perspectives:
(1) our approach offers flexible representations of tables suitable for characterizing diverse and complex table layouts;
(2) it better captures semantic information of a table in various subunits, hence can handle situations where queries are intended for different granularities of content.

\subsection{Pre-training on Semi-structured Data}
Some recent efforts have been made to pre-train graph neural networks for modeling structured or semi-structured data. Previous studies proposed node-level and graph-level pre-training tasks.
Node-level pre-training methods, including Variational Graph Auto-Encoders \cite{kipf2016variational}, GraphSAGE \cite{hamilton2017inductive}, Graph Infomax \cite{velivckovic2018deep}, and GPT-GNN \cite{hu2020gpt}, aimed to support downstream tasks that relied on node representations.
Graph-level pre-training methods, such as InfoGraph \cite{sun2019infograph}, sought to support inductive representation learning for global prediction tasks on graphs or subgraphs.
In addition, \citet{hu2019strategies} combined both node-level and graph-level pre-training.
Our pre-training process is connected to the supervised graph-level property prediction by \citet{hu2019strategies}, but we match the graph representations to textual representations.

Fewer works have attempted pre-training on tabular data.
Early work \cite{ghasemi2018tabvec, gol2019tabular} pre-trained embeddings for words or cells in tabular data according to co-occurrence.
Inspired by the recent success of BERT \cite{devlin2019bert} in language modeling, researchers extended BERT for encoding sequences extracted from tables and achieved state-of-the-art performance on semantic parsing over relational tables.
\citet{yin2020tabert} proposed TaBERT, which was pre-trained by recovering masked words, masked cells, and names and data types of masked columns.
\citet{herzig2020tapas} proposed TAPAS, which used a masked language model objective as BERT, but applied whole word and whole cell masking.
Those aforementioned techniques however, do not capture the diverse and complex layout structures of tables, nor do they support a way of multi-granular aggregation of table information, which are both essential to tackling the NLTR task.