Generating An Optimal Interview Question Plan Using A Knowledge Graph And Integer Linear Programming (2021)

Abstract: Given the diversity of the candidates and complexity of job requirements, and since interviewing is an inherently subjective process, it is an important task to ensure consistent, uniform, efficient and objective interviews that result in high quality recruitment. We propose an interview assistant system to automatically, and in an objective manner, select an optimal set of technical questions (from question banks) personalized for a candidate. This set can help a human interviewer to plan for an upcoming interview of that candidate. We formalize the problem of selecting a set of questions as an integer linear programming problem and use standard solvers to get a solution. We use knowledge graph as background knowledge in this formulation, and derive our objective functions and constraints from it. We use candidate’s resume to personalize the selection of questions. We propose an intrinsic evaluation to compare a set of suggested questions with actually asked questions. We also use expert interviewers to comparatively evaluate our approach with a set of reasonable baselines.

## introduction a large multi-national it company added roughly 70,000 employees in fy2018-19. 1 assuming an average interview time of 30 minutes, 3 interviewers in each interview, and 4 candidates interviewed for every position, implies approximately 420,000 person-hours were spent in one year just on conducting the interviews. given the diversity of the candidates and complexity of job requirements, and considering that interviewing is an inherently human and subjective process, it is a mammoth task to ensure consistent, uniform, efficient and objective interviews that result in high quality re-cruitment. ai and ml technologies are increasingly playing important roles in helping improve recruitment quality, e.g., @xcite , @xcite , @xcite , although ethical issues are emerging. 2 in this paper, we consider one particular way to assist human interviewers in improving the quality of their interviews and in reducing subjectivity. before conducting an interview, an interviewer typically studies the candidate's resume, noting salient points about her education, skills, job history, roles, projects, tasks handled etc. the interviewer also notes the apparent strengths and weaknesses of the candidate, as also the extent to which she matches (and does not match) the job profile for which she will be interviewed. in short, the interviewer builds an a priori rough mental profile of the candidate, and prepares a mental plan of how to interview her. such a plan includes preparing an unordered set of questions that the interviewer would like to ask the candidate. in this paper, we propose an interview assistant system to automatically, and in an objective, unbiased manner, build such a set of questions for a human interviewer, which can be part of a plan for an upcoming interview. we assume we have question banks from where questions can be selected. note that such a plan is static, and the actual sequence of questions asked by an interviewer may diverge from the static plan, due to dynamic and contextual reasons observed during the flow of the interview. such reasons include (i) mismatch between the interviewer's prior impression about the strengths of the candidate and the quality of the candidate's actual answers; (ii) the questions asked by other interviewers, if they are present. nevertheless, such a plan generated by the system is still useful, as it reduces the cognitive load on the interviewer, and brings some standardization and objectivity to an interview. having a systemsuggested set of questions, personalized for a particular candidate, before starting the interview is useful for the interviewer. the questions help in getting to a good start and also give ideas about where to focus during the interview. the novel contributions of this paper are as follows. we formalize the problem of selecting a set of questions as an integer programming optimization problem and use standard solvers to get a solution. we use knowledge graph as background knowledge, and formulate our objective functions and constraints from it. to our knowledge, this is the first paper to address the problem of creating an optimal interview plan. we report experiments on a real dataset of candidates and interview questions and compare against a state-of-the-art baseline using both intrinsic and human study based evaluation. the rest of the paper is organized as follows. section 2 summarizes related work, section 3 formulates the optimization problem, section 4 gives details of our novel evaluation measure, sectionrefsec:nlp describes the use of nlp techniques to build the requisite resources, section 6 describes the baselines used for comparison, section 7 describes the our experimental results, and section 8 concludes the paper. ## related work work in this paper is close to the field of computerized adaptive testing (cat) @xcite , where the task is to select questions (also called items) on-the-fly from a question bank, depending on how the student has answered the questions so far (i.e., adjusting to her ability level), with goals of creating shorter tests that yield better differentiation among students. cat techniques are used in large-scale general online examinations like gre, and in specialized medical licensing or certification examinations, e.g., in clinical pathology, emergency medicine, and pharmacy. we are not aware of any work on applying cat techniques to interviews. we first outline the key differences between our work and cat, which stem from the obvious differences between interviews and examinations. interviews are not really examinations, but are human, face-to-face, oral, and two-way interactions among a single candidate and possibly multiple interviewers. there is no set question paper, no rigid time-limit and interview questions need short free-form textual or spoken answers whereas cat deals mostly with examinations administering multiple-choice questions. unlike an examination, the interactions are two-way; e.g., the candidate can ask for clarification about a question. goals of an interview are different from that of an examination, e.g., assessing fitment for job position requiring multiple skills, rather than assessing depth and breadth in a fixed subject. students are anonymous in cat, whereas interviewers have detailed knowledge about the candidate; e.g., through her resume. cat is about a dynamically assembled, personalized, sequence of questions which are dependent on the student's answers so far, whereas in this paper we deal with a static one-time selection of interview questions, with no dynamic adjustment as per the candidate's answers i.e., in this paper we cannot estimate the candidate's latent abilities, since we do not have her answers. this prevents a direct comparison of our work with most cat techniques. see @xcite for a review of cat research. the key aspects of cat are: item selection criteria, content balancing (ensuring coverage of all sub-areas in the subject) and item exposure control (using randomization to prevent excessive item reuse across multiple examinations). many item selection approaches are formulated using item response theory and use information-theoretic criteria; e.g., fisher information @xcite , efficiency balanced information (ebi) @xcite , kullback-liebler information @xcite . various item exposure control methods have been proposed to reduce overuse of "good" items; see @xcite for a survey of early methods. while some cat systems use the above 3 aspects separately, the automated test assembly (ata) approaches use them together in an optimization framework such as linear programming or mixed integer programming, where content balancing criteria are constraints and item selection criteria are objective functions; e.g., theunissen (1986), der linden and boekkooi-timminga (1989), @xcite , @xcite . for a comparative analysis of such optimization approaches, see der @xcite and @xcite . again, it is difficult to directly compare our work with these optimizationbased approaches, because of our static setting in interviews where no answers are available to estimate candidate proficiency (unlike cat). in most cat approaches, the information available for each item is rather limited: subject, sub-area, difficulty level, discrimination level etc. we have used knowledge graphs to create a semantically rich and detailed characterization of questions in terms of concepts. our optimization formulation uses the knowledge graph to generate novel constraints (including content balancing) and objective functions for item selection. cat algorithms cannot be directly used as baselines, because (i) they output an ordered sequence of questions (we output an unordered set of questions); and (ii) they need candidate answers, which are not available to us. duerquiz @xcite starts from job descriptions and resumes of candidates, and considers the problem of recommending a set of questions using a skill graph. it uses knowledge of resumes of candidates who have been hired in the past. it additionally considers the task of extracting skills from resumes and job descriptions, and construction of the skill graph, which are not our primary focus. for the actual task of question selection for a specific resume, duerquiz initializes weights of concepts based on the job description, historical resumes and the focus resume, and then dissipates those weights over descendant concepts in the skill graph. finally, the weights determine the number of questions selected from a concept. it does not consider the notion of question difficulty, or relations between questions. ## problem formulation for concreteness, in this paper we focus on candidates in the it domain. we start by noting that an interviewer asks different types of questions. technical questions explore the breadth and depth of the candidate's understanding of a particular technical skill. other than technical questions, interviewers also ask techno-experience questions (e.g. about skills in projects), methodological questions, behavioural questions, among others. for concreteness, in this paper we focus only on technical questions about skills in the it domain. we focus on entry-level candidates (freshers or those with less than 1 year experience), because for more experienced candidates the interviewers tend to move quickly to technoexperience questions. we also assume the ques- figure 1 : the integer programming problem tions are such that they require short answers, typically containing up to 5-6 sentences. given a candidate resume r, a technical skill s, and a question bank qb s about that skill, the task we address is: how to select the "best" questions from qb s , which maximize some objective functions and meet the required constraints? the questions need to selected from qb s and need to be highly personalized for the candidate in the sense that they should be closely related to the candidate's background mentioned in r. the complete optimization formulation is given in fig. 1 . we use the term skill to refer to a broad technical area; examples: python, machine_learning, algorithms, networking etc. let s denote a given skill. let c s (or just c if the skill is clear) be a set of concepts related to a given skill. relationships such as is-a, has-a (inverse of is-part-of) hold between pairs of concepts; e.g., array is-a data_structure and class has-a method. we represent the concepts in a particular skill and their inter-relationships as a knowledge graph @xmath0, e, η), where the vertices are concepts, e is the set of directed edges linking pairs of con-cepts, and η : @xmath1. fig. 3 shows a small part of a concept graph for the skill python; here, each vertex corresponds to a concept, the edges show relationships between concepts and the edge label is shown on each arrow. neighbourhood of a concept @xmath2, denoted φ(u), is the set of concepts directly connected to u in the knowledge graph, along with u itself. for simplicity, we ignore the edge direction and edge label when computing φ(u). example: we assume we have a question bank, which is a set of questions about a particular skill, along with some other information with each question. formally, a question bank for a skill s is qb @xmath3, δ, λ), where q is a set of questions about s, the function δ(q) associates a difficulty level with every question @xmath4, and the function λ(q) associates a non-empty subset of concepts with every question @xmath5. 3 a difficulty level is 0 (easy), 1 (medium), 2 (hard); a more nuanced scale can be easily incorporated. fig. 2 shows a small question bank containing 13 questions for the skill python; it also shows the difficulty level and the subset of concepts (from the knowledge graph of fig. 3 ) associated with each question. in order to prevent the same subset of questions being identified by our solution for very similar resumes, we could either shuffle the questions in q, or use only a random subset of q as input. coverage of a question q, denoted ψ(q), is the set of concepts λ(q) associated with q, along with the concepts at 1-hop from each concept in λ(q). for simplicity, we ignore the edge direction and edge label when computing ψ(q). example: ψ(q 2 ) = {20, 21, 17, 24}. let x i , 1 ≤ @xmath6, where if x @xmath7, and not included if x @xmath8. then the first term f 1 in our objective function selects a set of questions which has the maximum coverage. different candidates can take different amounts of time t (q) for answering any particular question q in the qb. this time is candidate specific and unknown a priori. we have a simple model to accommodate this time: a candidate takes time t i (q) minutes to answer a question q having difficulty level δ(q) = i; for concreteness, we assume t 0 (q) = 1, t 1 (q) = 2, t 2 (q) = 3. this simplified model predicts the same time, for all candidates, for all questions having a particular difficulty level; a more nuanced approach would be, for example, to learn the time distribution from data of past interviews. interviewers often have an informal time-limit (budget) t on the time to spend on a particular skill. so we have constraint c1: the total estimated time taken to answer the selected questions must be at most t . in order to prevent selection of only easy questions, we introduce constraints {c2(j)} for @xmath9, 1, 2 that force a more equitable userspecified distribution of difficulty levels in selected questions. the user-specified constants 0 ≤ m 0 , m 1 , m 2 ≤ 1, m 0 + m 1 + m 2 = 1 give control to the user to generate questions that "suit" a particular "style"; e.g., setting m 0 = 0.2, m 1 = 0.2, m 2 = 0.6 will tend to select more hard questions. questions asked in an interview are often related to another question, indicating exploration of the depth of a candidate's knowledge. given a set of questions @xmath10, . . . , q k }, we define a question graph g a , whose vertices are the questions in a and two questions q i , q j have an undirected edge if λ(q i ) ∩ λ(q j ) = ∅. in general, g a may be a disconnected graph. a path of length 1 or more indicates a sequence of inter-related questions. fig. 4 shows the question graph for the questions in fig. 2 . a path p in a graph is a longest path (or chain) if p is not a sub-path of any other path in the graph. now we have another term f 2 in our objective function: maximize the sum of the lengths of all longest paths in g a . since this is computationally expensive, we can use as an approximation the number of edges in g a , since an edge indicates a sequence of two questions. note that this term has a quadratic form, which can be easily linearized taking advantage of the fact that the decision variables are all binary (we omit this reformulation). questions asked in an interview are often unrelated to another question, indicating exploration of the breadth of a candidate's knowledge. we define two questions q i , q j as unrelated if there is no path between them in g a i.e., q i is unreachable from q j and vice versa. analogously, we define two paths p 1 , p 2 in g a as unrelated if no vertex in p 2 is reachable from any vertex in p 1 and vice versa. now we have another term f 3 : maximize the number of pairs of paths which are unrelated. since this is computationally expensive, we can use as an approximation the number of pairs of vertices which are unreachable via paths from each other. note that this objective also has the quadratic form, which we linearize. an interview often includes questions about concepts related to a given skill which are mentioned in the candidate's resume r. let w @xmath11, w 2 , . . . , w ℓ } denote the ℓ concepts mentioned in the candidate's resume; e.g., in the descriptions of her jobs, projects, trainings etc. a reasonable interview must include questions related to as many concepts in the neighbourhood of w r as possible, giving us another objective function term f 4 . we can further refine this objective to specifically consider questions directly related to w r , giving us an additional term f d 4 , with w r instead of φ(w r ) and λ(q) instead of ψ(q). we could refine this even further, if we could estimate from the resume that the candidate has different proficiency levels in different concepts; e.g., if a candidate has worked in flash in 1 project of 3 months and in numpy in two projects for 11 months, then she is clearly stronger in numpy than in flash. analogously, let w j denote the set of concepts relevant to a given job description for which the candidate is being interviewed. a reasonable interview must include questions related to as many concepts in the neighborhood w j as possible, giving us term f 5 . as for f 4 , here as well we consider a direct version f d 5 , with w j replacing φ(w j ) and λ(q) replacing ψ(q). suppose we have some idea of the proficiency level η(s) that a particular candidate has in a given skill s. this estimate could be generated from the information in the resume (projects, tasks, trainings) or from other sources, such as the scores in a prior written test. suppose the estimated proficiency level in a skill is an integer from 0 (does not know) to 4 (expert). we should take this input into account in order to adjust the difficulty level of selected questions; e.g., a candidate with proficiency level η(s) = 3 should be asked fairly difficult questions. this gives us constraint c5, which says that the average difficulty level of selected questions should be above a user-specified constant h 0 , which can be derived from the proficiency level η(s) of the candidate in skill s. we normalize the terms in the objective function so that these take values in [0, 1]. further, we take a weighted sum (instead of the plain sum) of the terms: w 1 • f 1 + . . . + w 5 • f 5 , where w 1 , . . . , w 4 , w d 4 , w 5 , w d 5 are user-given positive real weights. the weights will allow the interviewer to change the relative importance of the terms. interview plans for a set of candidates: the optimization program discussed so far is useful to generate an interview plan for one particular candidate. however, in many situations (such as campus interviews), there is a sequence of interviews for multiple candidates and the system is required to generate a system plan for each of them. there are additional constraints on the set of interview plans generated in such a situation. for example, the repetition of questions across multiple candidates should be minimized i.e., different candidates (even those having a similar background) should by-and-large get different sets of questions. let n 0 denote the number of candidates to be interviewed in the current campaign. we assume that a single question bank qb s for skill s (or, just q for simplicity) will be used to select questions for each of the n 0 candidates. let gen_interview_plan denote the above optimization program for selecting questions for a given candidate. output of this program is a boolean vector sol, where sol(i) = 1 if question q @xmath12; 0 otherwise. we extend our earlier definition of a question bank by adding another property for each question viz., novelty count β(q i ), which is the n 0count(q i ), with count(q i ) being number of times the question q @xmath13. initially count(q i ) = 0 and β(q i ) = n 0 for each question in q. we sequentially call gen_interview_plan for each of the n 0 candidates and use the output boolean vector sol to increment β(q i ) for each question in q; see algorithm gen_interview_plan_set. again, we normalize this to ensure that the value is between 0 and 1. note that the novelty counts are updated for all questions after each call to the optimization program. integer programming being an np-hard problem, exact solvers often take a lot of time. instead, we resorted to the lp rounding approximation, where we relax the integer constraints x @xmath14, 1} to x @xmath15, 1] and used available lp solvers (cbc solver in python pulp) to solve the resultant linear programming problem. then we rounded the x i values to {0, 1} using a threshold. ## intrinsic evaluation while we do use human experts to compare two sets of questions, here we propose an automated intrinsic evaluation method to judge the quality of the set of questions (e.g., selected by our optimization model, or by any baseline method discussed later) for a particular candidate, by comparing this set with the set of questions actually asked to this candidate in a real interview. let a i denote the set of actual questions asked to i-th candidate, ignoring the order of asking; we can get a i from interview transcripts. let q i be the set of questions recommended by some algorithm for the i-th candidate. in general, we assume that both q i and a i are about the given skill s. suppose we have a boolean function is_qsim (discussed shortly) that returns t ru e if two given questions are "highly similar" and f alse otherwise. in forward evaluation, we compare each question q @xmath16, a k ) = t ru e and 0 otherwise. the quality of q i is evaluated based on the number of questions in q i having score 1. enforcing an additional constraint that a question in a i is "matched" to at most one question in q i , ensures that score qual f (q i ) is between 0 and 1. in backward evaluation, we compare each question a @xmath17, a j ) = t ru e and 0 otherwise. the quality measure qual b (a i ) is defined analogously. it remains now to define is_qsim. several similarity measures have been designed in the literature for short text similarity. for efficiency, we consider a simple measure: two questions are sim-ilar if their coverages share at least a required minimum number of concepts k 0 (which is a userspecified constant): ## nlp for interview resource creation while natural language processing does not play a direct role in the optimization formulation for the selection of interview questions, it is crucial for the creation of the prerequisite resources. the first task is the annotation of questions to identify concepts. these concepts are used to determine question coverage and to construct the question graph based on their coverage. we also use these annotations to construct the knowledge graph for skills, as we explain below. there is a rich body of literature in both mention detection and named entity disambiguation @xcite @xcite ). since we focus on skill-graphs which are largely sub-graphs of dbpedia, we use the publicly available apis from tagme @xcite . however, this resulted in two types of errors. many mentions were annotated with concepts irrelevant for our skills. secondly, many mentions relevant for our skills were left unannotated. we performed manual curation on the tagme annotations to correct these two types of errors. the second task is extraction of skills from resumes. we use an information extraction system called rinx @xcite , which uses gazetteer-based, linguistic patterns based machine learning methods (e.g., crf, bilstm) to extract mentions of various entity types and relations from resumes. for example, rinx extracts mentions of skill (e.g., machine_learning, python, concept (e.g., activation function, maximum margin), role (e.g., developer, dba, test_engineer), task (e.g., developed vendor master, performance tuning), among other entity types. the extracted skills are again annotated according to concepts by using tagme, and manually curated to correct errors. the next task is construction of the knowledge graph for different skills, based on the concept annotation of the questions and the extracted resume skills. this problem has not received enough attention in the computational linguistics community. we first identified a subgraph of dbpedia @xcite using the question concepts and the resume skill concepts as positive seeds. we then curated this knowledge graph manually to correct any errors. the next task is assigning difficulty levels to questions. this problem has also received very little attention @xcite . we use the following simple approach. use any automatic answer extraction technique to extract an answer text a for q, from a suitable corpus like wikipedia or a textbook. let λ(a) be the set of concepts associated with a. the degree d(u) of a concept vertex u in the knowledge graph, ignoring edge directions, is a good approximation of the "complexity" of that concept; a concept is complex, if it is directly related to many other concepts. thus the sum of the complexities of the individual concepts in the answer to a question is a good measure of the complexity of that question: γ(q) = @xmath18. we can now write simple rules to assign a difficulty level to each question: if γ(q) ≤ c 0 then δ(q) = 0 else if c 0 < γ(q) ≤ c 1 then δ(q) = 1 else δ(q) = 2 (c 0 , c 1 , c 2 are user-specified constants). more complex approaches, such as applying machine learning to predict difficulty levels for questions, are possible. finally, we identify similar questions for our evaluation. the is_qsim() function (eqn.3) uses overlap between annotated concepts for simplicity. clearly, there is a need for more sophisticated approaches, for example using paraphrase detection @xcite . ## baselines to compare against out integer programming approach (ip), we use the following baselines for selecting questions for a candidate having resume r: for our mip formulation, we use the following weights and hyper-parameters: w 1 = 100, w 2 = 100, w 3 = 100, w 4 = 30, w d 4 = 70, w 5 = 30, w d 5 = 70, m 0 = 0.3, m 1 = 0.4, m 2 = 0.3, h 0 = 0.9 and @xmath19. these weights were not finetuned, aside for t for controlling the number of recommended question. for duerquiz, the paper does not recommend any thumb rule for setting hyper-parameters. we set the propagation weight α @xmath20.85 by hand-tuning on one resume, and the smoothing weight β @xmath21.001. ## experimental results in this section, we describe our dataset derived from real interviews, and the experiments that we conducted using this dataset. we report comparisons of our proposed approach (ip) against the baselines defined in section 6 using both actual interview questions and as well as an user-study for evaluation. we leave out br2 and instead use its stronger version br3. all experiments were performed on an ubuntu 18.04.5 lts machine with 8-core intel i7-8550u 1.80ghz processors, and 16 gb memory. for ip, generation of questions with 45min time budget (∼ 25 questions) takes 155 secs on average. dataset: we constructed a knowledge graph of 714 concepts and 903 edges (avg. degree 2.51) from machine learning and deep learning. our question bank consists of 549 questions from these two skills. each question is annotated with concepts from the knowledge graph (1.18 concepts per question on average). finally, we use real resumes of 40 candidates (mostly fresh it graduates) interviewed by our organization over the last year. we identify knowledge graph concepts associated with their resumes (4.7 concepts per resume on average). for 20 of these candidates, we also have the actual questions asked to them during their interviews. of these, we consider only the questions related to our two topics of interest. the average number of questions per candidate is 5.05. ## conclusions and further work we have proposed an interview assistant system to automatically select an optimal set of technical questions (from a question bank) personalized for a candidate. we formalized the problem of selecting a set of questions from question banks as an integer programming problem, with multiple terms in the objective functions and multiple constraints. we used knowledge graph as background knowledge, and used the candidate's resume to personalize the selection of questions. we proposed a novel intrinsic evaluation to compare a set of suggested questions with actually asked questions in real interviews. we also used expert human interviewers to comparatively evaluate our approach with a set of reasonable baselines. our comparisons against state-of-the-art and ablated baselines show the usefulness of our proposed approach.