* Loucks-Horsley  _et al._ (2009) S. Loucks-Horsley, K. E. Stiles, S. Mundry, N. Love, and P. W. Hewson,  _Designing Professional Development for Teachers of Science and Mathematics_, Vol. 24 (SAGE Publications, 2009) p. 424.
  * Desimone  _et al._ (2002) L. M. Desimone, A. C. Porter, M. S. Garet, K. S. Yoon, and B. F. Birman, Educational Evaluation and Policy Analysis 24, 81 (2002).
  * Garet  _et al._ (2001) M. S. Garet, A. C. Porter, L. Desimone, B. F. Birman, and K. S. Yoon, American Educational Research Journal 38, 915 (2001).
  * Wilson (2013) S. M. Wilson, Science 340, 310 (2013).
  * Valli and Hawley (2002) L. Valli and W. D. Hawley, The keys to effective schools: Educational reform as continuous improvement , 86 (2002).
  * Henderson and Dancy (2008) C. Henderson and M. H. Dancy, American Journal of Physics 76, 79 (2008).
  * Dancy and Henderson (2007) M. Dancy and C. Henderson, Physical Review Special Topics - Physics Education Research 3, 010103 (2007).
  * O’Connor and Michaels (1993) M. C. O’Connor and S. Michaels, Anthropology and Education Quarterly 24, 318 (1993).
  * Goodwin (1990) M. H. Goodwin,  _He-said-she-said: Talk as Social Organization Among Black Children_ (Indiana University Press, 1990) p. 371.
  * Jurow (2005) A. S. Jurow, Journal of the Learning Sciences 14, 35 (2005).
  * Knuth and Peressini (2001) E. Knuth and D. Peressini, Mathematics Teaching in the Middle School 6, 320 (2001).
  * Lotman (1988) Y. M. Lotman, Soviet psychology 26, 32 (1988).
  * Bakhtin (1986) M. M. Bakhtin, Trans. VW McGee. Ed. C. Emerson and M. Holquist. Austin: University of Texas Press (1986).
  * Scott  _et al._ (2006) P. H. Scott, E. F. Mortimer, and O. G. Aguiar, Science Education 90, 605 (2006).
  * Hammersley-Fletcher and Orsmond (2005) L. Hammersley-Fletcher and P. Orsmond, Studies in Higher Education 30, 213 (2005).
  * Chism (2007) N. V. N. Chism,  _Peer review of teaching: a sourcebook_ , 2nd ed. (Anker Publishing Co., Bolton, MA, 2007).
  * Hammersley-Fletcher and Orsmond (2004) L. Hammersley-Fletcher and P. Orsmond, Studies in Higher Education 29, 489 (2004).
  * Aubusson  _et al._ (2010) P. Aubusson, J. Griffin, and F. Steele, Studying Teacher Education 6, 201 (2010).
  * Kane and Staiger (2011) T. J. Kane and D. O. Staiger, Bill & Melinda Gates Foundation (2011).
  * Guarino and Stacy (2012) C. Guarino and B. Stacy, Boulder, CO: National Education Policy Center. 28 (2012).
  * Amrein-Beardsley and Osborn Popp (2011) A. Amrein-Beardsley and S. E. Osborn Popp, Educational Assessment, Evaluation and Accountability 24, 5 (2011).
  * Hora and Ferrare (2013) M. T. Hora and J. Ferrare,  (2013).
  * Gallos  _et al._ (2005) M. R. Gallos, E. van den Berg, and D. F. Treagust, International Journal of Science Education 27, 985 (2005).
  * Morrell and Schepige (2012) P. D. Morrell and A. C. Schepige,  _Self-Studies of Science Teacher Education Practices_, edited by S. M. Bullock and T. Russell, Self-Study of Teaching and Teacher Education Practices, Vol. 12 (Springer Netherlands, Dordrecht, 2012) pp. 157–173.
  * MacIsaac  _et al._ (2001) D. MacIsaac, D. Sawada, and K. Falconer,  _Presented at the Annual Meeting of the American Educational Research Association_, Tech. Rep. (Seattle, WA, 2001).
  * Hampton and Reiser (2004) S. E. Hampton and R. A. Reiser, Research in Higher Education 45, 497 (2004).
  * McShannon  _et al._ (2006) J. McShannon, P. Hynes, N. Nirmalakhandan, G. Venkataramana, C. Ricketts, A. Ulery, and R. Steiner, Journal of Professional Issues in Engineering Education and Practice 132, 204 (2006).
  * Hativa (1995) N. Hativa, Research in Higher Education 36, 377 (1995).
  * Piccinin  _et al._ (2006) S. Piccinin, C. Cristi, and M. McCoy, International Journal for Academic Development 4, 75 (2006).
  * Horn and Little (2010) I. S. Horn and J. W. Little, American Educational Research Journal 47, 181 (2010).
  * van Es and Sherin (2002) E. A. van Es and M. G. Sherin, Journal of Technology and Teacher Education 10, 571 (2002).
  * van Es and Sherin (2008) E. A. van Es and M. G. Sherin, Teaching and Teacher Education 24, 244 (2008).
  * Sherin and van Es (2008) M. G. Sherin and E. A. van Es, Journal of Teacher Education 60, 20 (2008).
  * van Es and Sherin (2010) E. A. van Es and M. G. Sherin, Journal of Mathematics Teacher Education 13, 155 (2010).
  * Sawada  _et al._ (2002) D. Sawada, M. D. Piburn, E. Judson, J. Turley, K. Falconer, R. Benford, and I. Bloom, School Science and Mathematics 102, 245 (2002).
  * Wainwright  _et al._ (2003) C. L. Wainwright, L. B. Flick, and P. D. Morrell, Journal of Mathematics and Science: Collaborative Explorations 6, 21 (2003).
  * Smith  _et al._ (2013) M. K. Smith, F. H. M. Jones, S. L. Gilbert, and C. E. Wieman, CBE life sciences education 12, 618 (2013).
  * Hora  _et al._ (2013) M. T. Hora, A. Oleson, and J. J. Ferrare, Madison: Wisconsin Center for Education Research (2013).
  * West  _et al._ (2013) E. A. West, C. A. Paul, D. Webb, and W. H. Potter, Physical Review Special Topics - Physics Education Research 9, 010109 (2013).
  * Goodwin (1994) C. Goodwin, American Anthropologist 96, 606 (1994).
  * MacIsaac (2002) D. MacIsaac, The Physics Teacher 40, 479 (2002).
  * Wainwright  _et al._ (2004) C. Wainwright, P. D. Morrell, L. Flick, and A. Schepige, School Science and Mathematics 104, 322 (2004).
  * Turpen and Finkelstein (2009) C. Turpen and N. D. Finkelstein, Physical Review Special Topics - Physics Education Research 5, 020101 (2009).
  * Turpen and Finkelstein (2010) C. Turpen and N. D. Finkelstein, Physical Review Special Topics - Physics Education Research 6, 020123 (2010).
  * Adamson  _et al._ (2003) S. L. Adamson, D. Banks, M. Burtch, F. Cox, E. Judson, J. B. Turley, R. Benford, and A. E. Lawson, Journal of Research in Science Teaching 40, 939 (2003).
  * Budd  _et al._ (2013) D. A. Budd, K. J. v. d. H. Kraft, D. A. McConnell, and T. Vislova, Journal of Geological Education 61, 461 (2013).
  * Smith  _et al._ (2014) M. K. Smith, E. L. Vinson, J. A. Smith, J. D. Lewin, and M. R. Stetzer, CBE-Life Sciences Education 13, 624 (2014).
  * Morrell  _et al._ (2004) P. D. Morrell, C. Wainwright, and L. Flick, School Science and Mathematics 104, 199 (2004).
  * Walkington and Marder (2013) C. Walkington and M. Marder, “Classroom Observation and Value-Added Models Give Complementary Information about Quality of Mathematics Teaching,” (2013).
  * Stang and Roll (2014) J. B. Stang and I. Roll, Physical Review Special Topics - Physics Education Research 10, 020117 (2014).
  * Lund  _et al._ (2015) T. J. Lund, M. Pilarz, J. B. Velasco, D. Chakraverty, K. Rosploch, M. Undersander, and M. Stains, CBE-Life Sciences Education 14 (2015), 10.1187/cbe.14-10-0168.
  * Marshall  _et al._ (2010) J. C. Marshall, J. Smart, and R. M. Horton, International Journal of Science and Mathematics Education 8, 299 (2010).
  * Lane and Harris (2015) E. S. Lane and S. E. Harris, Journal of College Science Teaching 44, 83 (2015).
  * Gutiérrez  _et al._ (1999) K. Gutiérrez, D. Berlin, K. Crosland, and A. Razfar, Los Angeles: Center for the Study of Urban Literacies, Graduate School of Education and Information Studies, University of California, Los Angeles (1999).
  * van Zee and Minstrell (1997) E. van Zee and J. Minstrell, Journal of the Learning Sciences 6, 227 (1997).
  * Cazden (2001) C. B. Cazden, The language of teaching and learning (2001).
  * Mehan (1979) H. Mehan,  _Learning lessons_ (Harvard University Press Cambridge, MA, 1979).
  * Lemke (1989) J. L. Lemke,  (1989).
  * Engle and Conant (2010) R. A. Engle and F. R. Conant, Cognition and Instruction 20, 399 (2010).
  * Schwartz and Bransford (1998) D. L. Schwartz and J. D. Bransford, Cognition and Instruction 16, 475 (1998).
  * Hammer  _et al._ (2005) D. Hammer, A. Elby, R. E. Scherr, and E. F. Redish, Transfer of learning from a modern multidisciplinary perspective , 89 (2005).
  * Smith III  _et al._ (1994) J. P. Smith III, A. A. Disessa, and J. Roschelle, The Journal of the Learning Sciences 3, 115 (1994).
  * Disessa and Sherin (1998) A. A. Disessa and B. L. Sherin, International Journal of Science Education 20, 1155 (1998).
  * Scherr and Hammer (2009) R. E. Scherr and D. Hammer, Cognition and Instruction 27, 147 (2009).
  * Markauskaite and Goodyear (2014) L. Markauskaite and P. Goodyear, Learning, Culture and Social Interaction 3, 237 (2014).
  * Hora (2012) M. T. Hora, The Review of Higher Education 35, 207 (2012).
  * Cohen  _et al._ (2003) D. K. Cohen, S. W. Raudenbush, and D. L. Ball, Educational Evaluation and Policy Analysis 25, 119 (2003).
  * Stroupe (2013) D. Stroupe,  _“Students drive where I go next”: Ambitious practice, beginning teacher learning, and classroom epistemic communities_ , Ph.D. thesis, University of Washington (2013).
  * Harlow  _et al._ (2013) D. B. Harlow, J. A. Bianchini, L. H. Swanson, and H. A. Dwyer, Journal of Research in Science Teaching 50, 1098 (2013).
  * Dancy and Henderson (2009) M. Dancy and C. Henderson, in  _Physics Education Research Conference 2009_ (PER Conference, Ann Arbor, MI, 2009) pp. 121–124.
  * Horn (2010) I. S. Horn, The Teachers College Record 112, 225 (2010).
  * Henderson  _et al._ (2014) C. Henderson, C. Turpen, M. Dancy, and T. Chapman, Physical Review Special Topics - Physics Education Research 10, 010106 (2014).
  * Dancy  _et al._ (2010) M. H. Dancy, C. Turpen, and C. Henderson, in  _Physics Education Research Conference 2010_ (PER Conference, Portland, OR, 2010) pp. 117–120.
  * Turpen  _et al._ (2016) C. Turpen, M. Dancy, and C. Henderson, Physical Review - Physics Education Research 12, 010116 (2016).
  * Prather and Brissenden (2008) E. E. Prather and G. Brissenden, Astronomy Education Review 7, 1 (2008).
  * Darling-Hammond  _et al._ (2009) L. Darling-Hammond, R. C. Wei, A. Andree, N. Richardson, and S. Orphanos, Washington, DC: National Staff Development Council (2009).
  * Bandura (1986) A. Bandura,  _Social foundations of thought and action: A social cognitive theory._ (Prentice-Hall, Inc, 1986).
  * Lund and Stains (2015) T. J. Lund and M. Stains, International Journal of STEM Education 2, 13 (2015).
  * Judson and Lawson (2007) E. Judson and A. E. Lawson, Journal of Research in Science Teaching 44, 490 (2007).
  * Chappell (2007) A. Chappell, Journal of Geography in Higher Education 31, 257 (2007).
  * Rundquist  _et al._ (2015) A. Rundquist, J. Corbo, S. Chasteen, M. Martinuk, C. Henderson, and M. Dancy, in  _Physics Education Research Conference 2015_ (College Park, MD, 2015) pp. 279–282.
  * Oleson and Hora (2013) A. Oleson and M. T. Hora, Higher Education 68, 29 (2013).
  * Seymour (2000) E. Seymour,  _Talking about leaving: Why undergraduates leave the sciences_ (Westview Press, 2000).
  * Halley  _et al._ (2011) J. Halley, A. Eshleman, and R. M. Vijaya,  _Seeing white: An introduction to white privilege and race_ (Rowman & Littlefield Publishers, 2011).
  * Carlone (2004) H. B. Carlone, Journal of Research in Science Teaching 41, 392 (2004).
  * Steele (1997) C. M. Steele, The American psychologist 52, 613 (1997).
  * Johnson (2007) A. C. Johnson, Science Education 91, 805 (2007).
  * Robertson (2015) A. D. Robertson,  _Responsive Teaching in Science and Mathematics_ (Routledge, 2015).
  * Coffey  _et al._ (2011) J. E. Coffey, D. Hammer, D. M. Levin, and T. Grant, Journal of Research in Science Teaching 48, 1109 (2011).
  * National Research Council (2012) National Research Council,  _A Framework for K-12 Science Education: Practices, Crosscutting Concepts, and Core Ideas_ (National Academies Press, 2012).
  * Singer (1996) E. R. Singer, Research in Higher Education 37, 659 (1996).
  * Note (1) The R-PDOT interface can be accessed at http://gorp.ucdavis.edu.
  * Landis and Koch (1977) J. R. Landis and G. G. Koch, biometrics , 159 (1977).
  * Note (2) The original ColorBrewer (v1.0) was funded by the NSF Digital Government program during 2001–02, and was designed at the GeoVISTA Center at Penn State (National Science Foundation Grant No. 9983451, 9983459, 9983461). The design and rebuilding of the new version (v2.0) was donated by Axis Maps LLC, winter 2009 and updated in 2013.
  * Note (3) Currently, the Python scripts used to generate these timelines and all other representations shown can be obtained on the Digital Repository at the University of Maryland (DRUM) or by contacting the lead author. Ultimately, we anticipate that these visualizations will be generated automatically following data collection on the GORP website, and the original Python scripts will be downloadable from a GORP repository.
  * Olmstead and Turpen (2015) A. Olmstead and C. Turpen, in  _Physics Education Research Conference 2015_ , PER Conference (College Park, MD, 2015) pp. 243–246.
  * Note (4) On a post-workshop evaluation survey, faculty’s ratings of the “usefulness” of Session C was lower than for many other sessions at that iteration of the NFW.

##  Appendix A Extended R-PDOT codebook: Type-of-engagement

_Code name_ |  _Code description_ |  _Example observed behaviors and actions_
---|---|---
Workshop Leader Lecture |  Workshop leader lectures while faculty participants listen. |  -Workshop leader lecturing on a pre-determined topic.
-Workshop leader asking a rhetorical question.
Large Group Closed,
Faculty Participant Question |  Large group closed discussion. Faculty participant(s) question the workshop leader, and (optionally) the workshop leader answers through lecturing, while all other participants listen. |  -Faculty participants challenging the workshop leaders’ ideas.
-A workshop leader engaging in conversation with a questioner(s), with little or no participant-participant interaction.
-A workshop leader addressing a participant’s question at length, i.e., the workshop leader’s turns of talk are significantly longer than faculty participants’ turns of talk.
Large Group Closed,
Workshop Leader Question |  Large group closed discussion. Workshop leader asks non-rhetorical closed questions, and (optionally) one or more faculty participants respond directly to the workshop leaderDancy and Henderson (2007). |  -Faculty participants voting in response to a multiple-choice question.
-Participants contributing in short phrases or full sentences in response to a workshop leader’s question.
-Workshop leader and a few faculty participants taking turns speaking, with the discourse focused on revealing an answer the workshop leader is seeking.
-A workshop leader revoicing participant responses.
-A workshop leader intentionally making an implementation “error” and expecting participants to pause him/her.
-A workshop leader reading a question or prompt aloud.

Large Group Open Discuss |  Large group open discussion. Workshop leader and faculty participants take turns speaking, with the discourse focused on the ideas of faculty participantsDancy and Henderson (2007). |  -Faculty participants speaking in complete sentences and contributing new ideas.
-A workshop leader asking open-ended questions and facilitating discussion between faculty participants.
-Workshop leader(s) participating in discussion in a non-authoritative manner, e.g., sharing their own experiences without privileging them over participants’ experiences.

Small Group Discuss |  Faculty participants discuss with each other in small groups. |  -Faculty discussing with their peers during Peer Instruction.
-Faculty collaborating on assigned tasks.
-Faculty discussing ideas about teaching and learning in response to a prompt.
-A workshop leader giving brief instructions while most faculty are still discussing with each other.

Faculty Participant Present |  One or more faculty participants present to all others. |  -Faculty participants reporting out after working on a task in small groups.
-Faculty participants reporting out after working independently.
-Workshop leader facilitating presentations, e.g., calling on the next group to speak or revoicing faculty’s contributions.
Faculty Participant
Independent Work |  Faculty participants work independently on a task. |  -Faculty participants silently reading a Peer Instruction question.
-Faculty participants watching classroom video.
-Faculty participants writing independently in response to a prompt or task.

##  Appendix B Extended R-PDOT codebook: Focus-of-engagement

_Code name_ |  _Code description_ |  _Example observed behaviors and actions_
---|---|---
Workshop Instructions |  Workshop leader instructs participants about what they should or will be doing during the workshop (or participants attempt to clarify these instructions). |  -Workshop leader describing the intended purpose of the workshop or workshop session.
-Workshop leader telling faculty how to act or what to focus on during an upcoming workshop task.
-Faculty recounting or attempting to clarify the instructions for a workshop task.

Education Research Theory and Results |  Workshop leader and/or participants emphasize discipline-based education research processes, principles, or findings. |  -Describing student misconceptions identified in research.
-Showing evidence of improved student outcomes in active learning environments.
-Discussing the implications of active learning for diverse student populations.
-Describing or making sense of education research methods and results.
-Describing the characteristics or demographics of students within a particular study.
-Describing or discussing research-motivated principles in relation to teaching decisions.

Instructional Strategies (IS)
Description and Purpose |  Workshop leader and/or participants show or describe active learning strategies ranging from current faculty practices to strongly research-based instructional strategies. |  -Listing and describing research-based instructional strategies.
-Providing instructions about where to find existing materials or questions.
-Showing the specific steps that comprise an active learning instructional strategy.
-Describing or discussing the purpose of any active learning instructional strategy or components within it.
-Describing or discussing the functionality associated with research-based educational technologies (such as PhET sims).
-Displaying and briefly discussing research-based questions or tasks.
-Describing or discussing possible outcomes of using a particular research-based instructional strategy.

Workshop Leader (WL)
Simulating IS |  Faculty participants experience a workshop leader’s implementation of an instructional strategy, either by acting as mock students, or through observing video, transcript, or case study narrative. |  -A workshop leader assuming the role of a science instructor to implement a research-based instructional strategy.
-A workshop leader assuming the role of a science instructor to demonstrate common faculty practices.
-A workshop leader showing classroom video.
-Faculty participants reading a detailed classroom case study.
-Faculty participants working through a science task as mock students.

Faculty Participant (FP)
Simulating IS (as educator) |  A predetermined subset of faculty participants (one or more) try out implementing an instructional strategy while other participants act as mock students. |  -Individual faculty participants implementing a research-based instructional strategy with others acting as students.
-Teams of faculty participants implementing a research-based instructional strategy with others acting as students.
-Faculty participants rehearsing the implementation of a research-based instructional strategy in small groups.

Analyzing Simulated IS |  Workshop leader and/or participants reflect on (analyze, critique, evaluate, justify) a shared experience of someone simulating an instructional strategy in situ. |  -Analyzing how students responded to a given instructor move or reasoned through a science task.
-Analyzing the behaviors and actions of an instructor observed during the workshop session.
-Reflecting on the quality of faculty participants’ engagement in the workshop.
-Predicting how students would respond to alternative instructor moves compared to those seen or experienced.
-Generating possible next steps an instructor could take following a scenario experienced or considered in the workshop.
-Analyzing a hypothetical situation that is closely related to, and generated in relation to, an in situ implementation of an instructional strategy.

---|---|---
WL Pre-Workshop Experiences |  Workshop leader and/or participants discuss a workshop leader’s past experiences, including instructional goals, practices, values, and local contexts. |  -A workshop leader describing their involvement in discipline-based education research and prior studies they have done, using first-person narrative.
-A workshop leader describing their teaching practices.
-Participants eliciting a workshop leader’s past experiences, such as the details of how they teach and the characteristics of their students.

FP Pre-Workshop Experiences |  Workshop leader and/or participants reflect on participants’ past experiences, including instructional goals, practices, values, and local contexts. |  -Faculty participants describing specific teaching strategies they have implemented in their classrooms.
-A workshop leader eliciting or stating assumptions about faculty participants’ prior teaching and learning experiences.
-Faculty participants describing their local teaching resources or constraints.

Student Experiences |  Workshop leader and/or participants consider students’ knowledge, skills, or affect. |  -Hypothesizing about or describing known student explanations of science ideas.
-Analyzing real student discourse or student work.
-Describing student resistance or buy-in to different instructional approaches and discussing possible causes.
-Discussing students’ disciplinary knowledge and skills, and considering implications for instruction.
-Describing student demographics or characteristics

Disciplinary Content
Knowledge |  Workshop leader and/or participants consider disciplinary ideas. |  -Faculty participants engaging in disciplinary tasks using skills and knowledge that students would likely use.
-Faculty participants making sense of a task using a broad range of skills and knowledge (potentially including advanced disciplinary ideas).
-A workshop leader lecturing or asking questions that require knowledge from the participants’ own discipline, e.g., as part of simulating a research-based instructional strategy.

Analyzing and/or Creating
Student Tasks |  Participants create, modify, or evaluate and/or workshop leaders critique or evaluate specific materials, questions, or tasks for students. |  -Writing new questions during the workshop.
-Critiquing existing questions or tasks.
-Highlighting effective aspects of existing specific research-based materials, questions, or tasks.
-Classifying questions using Bloom’s taxonomy.
-Exploring the pedagogical affordances or constraints of a specific instructional strategy simulation.

Planning for FP
Future Teaching |  Workshop leader advises and/or faculty participants plan next steps for when participants go back to their home institutions. |  -Discussing possible ways to adapt research-based instructional strategies to fit participants’ local contexts.
-Advising faculty participants about how to approach the process of changing their teaching.
-Faculty participants identifying questions or tasks that are particularly relevant for their own instructional goals.


# Self-learn to Explain Siamese Networks Robustly

Chao Chen1, Yifan Shen2, Guixiang Ma3, Xiangnan Kong4, Srinivas Rangarajan5,
Xi Zhang2, Sihong Xie1  1Computer Science and Engineering Dept, Lehigh
University 2Laboratory of Trustworthy Distributed Computing and Service (MoE),
BUPT, 3University of Illinois at Chicago, 4Worcester Polytechnic Institute,
5Department of Chemical and Biomolecular Engineering, Lehigh University
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Learning to compare two objects are essential in applications, such as digital
forensics, face recognition, and brain network analysis, especially when
labeled data are scarce and imbalanced. As these applications make high-stake
decisions and involve societal values like fairness and transparency, it is
critical to explain the learned models. We aim to study post-hoc explanations
of Siamese networks (SN) widely used in learning to compare. We characterize
the instability of gradient-based explanations due to the additional compared
object in SN, in contrast to architectures with a single input instance. We
propose an optimization framework that derives global invariance from
unlabeled data using self-learning to promote the stability of local
explanations tailored for specific query-reference pairs. The optimization
problems can be solved using gradient descent-ascent (GDA) for constrained
optimization, or SGD for KL-divergence regularized unconstrained optimization,
with convergence proofs, especially when the objective functions are nonconvex
due to the Siamese architecture. Quantitative results and case studies on
tabular and graph data from neuroscience and chemical engineering show that
the framework respects the self-learned invariance while robustly optimizing
the faithfulness and simplicity of the explanation. We further demonstrate the
convergence of GDA experimentally.

33footnotetext: This author now works at Intel Labs.

##  I Introduction

Figure 1:  Explaining Siamese networks with invariant. Left: major feature
vectors $\mathbf{z}$ can be converted to minor feature vectors $\mathbf{x}$ by
one-hot encoding, and the SN predicts the similarity of the query
$\mathbf{x}^{s}$ and reference $\mathbf{x}^{t}$. Right: SN explanation (SNX)
for tabular data is enclosed in the dash-lined box. The workflow of SNX on
graph data is similar but selects edges (see Fig. 2). Global invariant salient
features for Alice are {Age, Deposits}, on both the major and minor levels
(light purple values and boxes). The comparisons of Alice with references Bob
and Charles lead to different local explanations (dark purple boxes), with two
minor features selected beyond global invariant features.

Siamese networks (SN for short in the sequel) [5] are widely used in
similarity metric learning [6, 30] and contrastive learning [4, 18] where
objects are compared. The applications of SN include digital forensics [7],
face recognition [6], and brain network analysis [30]. Different from
conventional architectures that take one input instance, an SN maps a pair of
instances (the “query” and the “reference”) to a similarity score [36]. As an
example, in Fig. 1, an SN is used to compare credit card applicants, those of
which differ from the current cardholders will be rejected. As SN is widely
used in high-stake applications involving societal values, it is urgent to
provide simple and convincing explanations [15], to improve SN fairness and
trustworthiness[26].

Challenges. We focus on post-hoc explanations of SN, represented by a small
number of salient input elements that closely approximate the prediction made
on the original input [38, 32]. On the one hand, in contrast to explaining
architectures with one single input [38, 48], explanations for SN should
consider both query and reference, and explanations insensitive to either one
of them [36] are misleading. On the other hand, the additional reference can
make the explanation over-sensitive to irrelevant perturbations. A good
explanation should be an invariant pertaining to the fixed query and
reference. For example, in Fig. 1, with the same prediction (“different
classes”) on two query-reference pairs, Alice-Bob and Alice-Charles, the
corresponding explanations should differ as the reference changes from Bob to
Charles. However, if the SN does encode certain invariant properties of Alice,
both explanations should faithfully respect the invariance, regardless of any
superfluous variations in the references.

Beyond tabular data in the illustrating example, SN is used in graphs [30],
and thus the explanation for the query calls for invariant subgraphs,
similarly. Neuroscience studies have shown that the global Default Mode
Network (DMN) [37] consisting of several brain regions of interest (ROI)
involves multiple cognitive and affective functions, such as emotional
processing and self-referential mental activity. Researchers interested in the
connections among the ROIs in a query bipolar patient [52] can require an
invariant subgraph of the ROIs to be respected when explaining the difference
between the query with healthy reference controls. In molecules, some specific
chemical sub-structures lead to properties, such as solubility and
insolubility [11], and such sub-structures can be considered as the invariant
of the molecule graphs. However, in many scenarios, obtaining labeled data or
domain knowledge to specify such invariants can be extremely costly.

Proposed Method. To control superfluous variations, we find invariants in the
form of global salient features for each individual instance using self-
supervision on unlabeled data. We then formulate a constrained optimization
problem to adapt the invariant saliency map to explain an SN prediction local
to a query-reference pair. The adaptation balances the conformity to the
invariance and the local flexibility when comparing a query to different
references111 “Global” means “regardless of the references compared with a
query”, rather than the universal behaviors of the explained model over the
entire data space [29].. For example, in Fig. 1, invariant features
{Age,Deposits} characterizing Alice are refined to specific values as
explanations local to different references. Similarly, global invariant
subgraphs of ROIs important to a subject are adapted when comparing the
subject with multiple references (see Fig. 8). We design a gradient descent
ascent (GDA) algorithm SNX (SN Explainer) to solve the constrained
optimization problems. Alternatively, we formulate an unconstrained
optimization problem with KL-divergence regularization (SNX-KL) to be solved
by stochastic gradient descent (SGD). The objective functions are nonconvex
due to the SN architecture, and we prove the convergence of GDA based on
nonconvex minimax optimization [25].

Based on the general framework, the optimization problem can be specialized to
incorporate additional constraints. One-hot encoding is widely used on tabular
datasets to help model optimization and meet domain-specific requirements
[21]. In Fig. 1, we have three binary features (called “minor” features) to
represent the three values (young, midlife, and old) of the feature Age
(called “major” features). One-hot encoding places constraints over local
explanations: a major categorical feature is salient if and only if at least
one of the associated minor binary features is salient. Local explanations on
the same query but different reference instances should select different
binary minor features under the same major features (e.g., Age and Deposits)
that globally characterize the query. Prior methods explaining SN [36, 43] are
designed for images without such constraints. See Section III-B for details.

Regarding graph data, explaining the predicted similarity by subgraphs
enumeration is NP-hard. Recent graph explanation approaches treat the edges
independently, possibly leading to less coherent subgraphs that are not
interpretable, as larger connected subgraphs can have biological or chemical
significance [48, 20]. We introduce structural constraints to make adjacent
edges more likely to be selected into a subgraph as global invariant
characterization of each graph, before finding local explanations between a
query and reference graphs. See Section III-C for details.

Contribution. 1) We formulate the explanations of SN as two optimization
problems. 2) We propose SNX-KL and SNX to solve the optimization problems with
convergence guarantee theoretically and experimentally. 3) We demonstrate that
self-supervised learning can find meaningful invariants to regulate local
explanations, and our algorithms outperform state-of-the-art explainers in six
datasets with respect to faithfulness, counterfactual and conformity. 4) We
analyze case studies on tabular and graph data.

##  II Problem Definition

###  II-A Data with structures

Tabular data is a set of vectors, each with the same list of $q$ categorical
major features $\mathbf{z}=[z_{1},\dots,z_{q}]$, such as age and deposits of a
credit card applicant [16, 21]222Continuous features can be discretized into
categorical features for the sake of explainable machine learning and domain-
specific requirements.. Using one-hot encoding, each major feature $z_{i}$ is
transformed to a set of binary minor features $x_{i,j}\in\\{0,1\\}$, where
$x_{i,j}=1$ if $z_{i}$ takes the $j$-th possible value. As a result,
$\sum_{j}x_{i,j}=1,\forall i=1,\dots,q$. The minor feature vector
$\mathbf{x}\in\\{0,1\\}^{p}$ is the concatenation of all binary minor
features, and $p$ is the number of minor features. One-hot encoding allows
mixed types of features, including special flags without ordinal semantics, to
be treated uniformly, and explanations extracted from one-hot vectors are more
actionable for recourse [42], for example, by telling an applicant to increase
the deposit to “$\geq 500$” rather than just “the deposit amount causes the
rejection”. Continuous features in different scales can be discretized and
one-hot-encoded to facilitate numerical optimization [2].

Graph data is a set of graphs, and each graph $G=(V,E)$ contains a set of
vertices $V$ and edges $E\subset V\times V$. We assume $G$ is undirected and
its adjacency matrix $A$ is symmetric: $A_{ij}=A_{ji}=1$ if nodes $v_{i}\in V$
and $v_{j}\in V$ are connected. To unify the descriptions of optimization
problems, $A$ is flattened to a vector $\mathbf{x}$ of length
$(|V|-1)(|V|-2)/2$ due to symmetry. For different graphs, $\mathbf{x}$ can be
of different lengths. We adopt a GNN that considers node attributes, but we
focus on extracting subgraphs and retain all node features and therefore do
not explicitly denote node features. Table I lists the symbols.

###  II-B Siamese Networks

An SN accepts a pair of instances, denoted as query
$\mathbf{x}^{s}\in\mathbb{R}^{p_{s}}$ and reference
$\mathbf{x}^{t}\in\mathbb{R}^{p_{t}}$ [36], with $p_{s}=p_{t}$ for two
vectors, and $p_{s}\neq p_{t}$ in general for two different graphs. The
superscript $s$ or $t$ will be omitted when referring to a single instance in
general. The SN consists of a mapping function
$emb(\mathbf{x};\boldsymbol{\theta})$ that maps $\mathbf{x}^{s}$ and
$\mathbf{x}^{t}$ to a latent space, where a metric measures the similarity
between the two embeddings. The mapping function
$emb(\mathbf{x};\boldsymbol{\theta})$ can be an MLP for vectors and a GNN for
graphs [11]. The similarity metric $sim(\cdot,\cdot)$ can be cosine
similarity. The SN is then the composite function
$f(\mathbf{x}^{s},\mathbf{x}^{t};\boldsymbol{\theta})=sim(emb(\mathbf{x}^{s};\boldsymbol{\theta}),emb(\mathbf{x}^{t};\boldsymbol{\theta}))$.
$f$ is trained to maximize (minimize, resp.) the similarity between any two
instances of the same class (different classes, resp.) using some loss
function $\ell^{\textnormal{SN}}$ as follows,

$\displaystyle\min_{\boldsymbol{\theta}}$
$\displaystyle\sum_{(s,t)\in\mathcal{T}}\ell^{\textnormal{SN}}(f(\mathbf{x}^{s},\mathbf{x}^{t};\boldsymbol{\theta}),y_{st}),$

where $\mathcal{T}$ is the training set containing all query-reference pairs.
The label of a pair $(\mathbf{x}^{s},\mathbf{x}^{t})$ is
$y_{st}=\text{1}[y^{s}=y^{t}]$, and is 1 if and only if the two instances have
the same class label ($y^{s}=y^{t}$).

TABLE I: Notation Definitions Notation | Definition
---|---
$\mathbf{z}$ |  A vector of $q$ categorical features in tabular data
$G=(V,E)$ |  A graph with sets of nodes $V$ and edges $E$
$A$ |  Adjacent matrix of $G$
$\mathbf{x}$ |  A vector of $p$ binary features encoding $\mathbf{z}$ or $A$
$f(\cdot,\cdot;\boldsymbol{\theta})$ |  The target Siamese Network with parameter $\boldsymbol{\theta}$
$(\mathbf{x}^{s},\mathbf{x}^{t}),y_{st}$ | Query and reference instances and the pair’s label
$\mathbf{N},\mathbf{n}$ |  Global and local masks over $\mathbf{z}$ (tabular data only)
$\mathbf{M},\mathbf{m}$ |  Global and local masks over binary vector $\mathbf{x}$

###  II-C Post-hoc explanation of SN

We assume a trained SN $f(\mathbf{x}^{s},\mathbf{x}^{t};\boldsymbol{\theta})$
and focus on explaining the SN’s predictions on test data. The parameter
$\boldsymbol{\theta}$ is fixed and thus omitted from
$f(\mathbf{x}^{s},\mathbf{x}^{t};\boldsymbol{\theta})$ when there is no
confusion. Given a pair of query $\mathbf{x}^{s}\in\\{0,1\\}^{p_{s}}$ and
reference $\mathbf{x}^{t}\in\\{0,1\\}^{p_{t}}$,
$\mathbf{m}^{s}\in[0,1]^{p_{s}}$ and $\mathbf{m}^{t}\in[0,1]^{p_{t}}$ are the
corresponding multiplicative masks. A large element in a mask indicates that
the corresponding feature value contributes more to the SN prediction [48,
40]. The element-wise product $\mathbf{m}\otimes\mathbf{x}$ is a masked
instance so that $\mathbf{m}_{i}\mathbf{x}_{i}\in[0,1]$ is the
importance/saliency of the $i$-th element of $\mathbf{x}$. Fig. 2 demonstrates
masked vector and graph instances. Additive perturbations [43, 38, 28] are
less interpretable, as the binary features can perturbed to outside the range
$[0,1]$. A prediction $f(\mathbf{x}^{s},\mathbf{x}^{t})$ depends on both
inputs $(\mathbf{x}^{s},\mathbf{x}^{t})$, so does the prediction’s
explanation. Such dependencies lead to robustness issues of the gradient-based
explanations.

Robustness of SN explanations. Using a simple example SN
$f(\mathbf{x}^{s},\mathbf{x}^{t};\boldsymbol{\theta})=\sigma(<\boldsymbol{\theta}^{\top}\mathbf{x}^{s},\boldsymbol{\theta}^{\top}\mathbf{x}^{t}>)$,
we characterize the robustness of gradient-based explanations of SN. Taking
the gradient of $\ell^{\textnormal{SN}}$ with respect to the query
$\mathbf{x}^{s}$, we obtain a saliency map over $\mathbf{x}^{s}$ proportional
to $\boldsymbol{\theta}\boldsymbol{\theta}^{\top}\mathbf{x}^{t}$. The salient
map explains the prediction using the magnitudes of elements in
$\boldsymbol{\theta}\boldsymbol{\theta}^{\top}\mathbf{x}^{t}$ and depends on
the SN parameter $\boldsymbol{\theta}$ and the reference $\mathbf{x}^{t}$. The
saliency map can be manipulated to any pre-defined target explanation
$\tilde{\mathbf{m}}^{s}$, by perturbing the reference $\mathbf{x}^{t}$:

$\textnormal{min}_{\boldsymbol{\delta}\in\mathbf{R}^{p_{t}}}\|(\boldsymbol{\theta}\boldsymbol{\theta}^{\top})(\mathbf{x}^{t}+\boldsymbol{\delta})-\tilde{\mathbf{m}}^{s}\|_{2}^{2}\hskip
14.45377pt\textnormal{s.t.}<\mathbf{x}^{s},(\boldsymbol{\theta}\boldsymbol{\theta}^{\top})(\boldsymbol{\delta})>=0.$

The objective pushes the saliency map to the target mask
$\tilde{\mathbf{m}}^{s}$ [9, 14], while the equality constraint specifies the
orthogonality and that the SN prediction is not changed. Simple algebra
manipulations lead to the problem of finding a vector $\mathbf{x}^{\perp}$
that is orthogonal to $\mathbf{x}^{s}$. Since the one-hot encoding or a large
number of disconnected pairs of vertices on a graph results in a large number
of zeros in $\mathbf{x}^{s}$, there are many vectors orthogonal to
$\mathbf{x}^{s}$. $\boldsymbol{\delta}$ can then be found by minimizing the
loss
$\|(\boldsymbol{\theta}\boldsymbol{\theta}^{\top})\boldsymbol{\delta}-\mathbf{x}^{\perp}\|_{2}^{2}$
without constraint.

Figure 2:  Left: a vector of major features, with globally salient features in
light purple and the corresponding minor feature vector, with local salient
features in dark purple. Right: the clique in light purple is a globally
salient subgraph, while an additional edge $(v_{1},v_{3})$ is considered
salient when a reference graph is compared.

Desiderata. We aim to find local explanations (i.e., masks, denoted by
$\mathbf{m}$ in general), with the following merits:

  * •

Simplicity [38] of an explanation derived from $\mathbf{m}$ is measured by the
number of features or edges of most important according to $\mathbf{m}$, or
$\|\mathbf{m}\|$, the $\ell_{1}$ norm of $\mathbf{m}$.

  * •

Faithfulness [38, 28] can be evaluated by feeding the masked instances
$(\mathbf{m}^{s}\otimes\mathbf{x}^{s},\mathbf{m}^{t}\otimes\mathbf{x}^{t})$ to
the target SN $f$ and measuring the distortion in the original output:

$\ell(f(\mathbf{x}^{s},\mathbf{x}^{t}),f(\mathbf{m}^{s}\otimes\mathbf{x}^{s},\mathbf{m}^{t}\otimes\mathbf{x}^{t})),$
(1)

where $\ell$ is some loss functions, such as the binary cross-entropy. A low
faithfulness loss indicates that the masks can select salient features to
preserve the SN output $f(\mathbf{x}^{s},\mathbf{x}^{t})$. Faithfulness and
simplicity are conflicting goals: the all-one mask retains all salient
features but will lose simplicity.

  * •

Counterfactuals (CF) can be more interpretable and helpful for algorithmic
recourse [45]. A CF explanation is the complement $(1-\mathbf{m})$ of a given
explanation $\mathbf{m}$ and can show “what” would the predictions be “if”
keeping the non-salient features. In Fig. 2, the counterfactual explanations
are the non-purple elements. We define the following counterfactual loss to
measure how much $\mathbf{m}^{s}$ and $\mathbf{m}^{t}$ fail to preserve:

$\ell(f(\mathbf{x}^{s},\mathbf{x}^{t}),f((1-\mathbf{m}^{s})\otimes\mathbf{x}^{s},(1-\mathbf{m}^{t})\otimes\mathbf{x}^{t})).$
(2)

If the masks have high weights over all salient features, then their
complements should distort the original SN prediction
$f(\mathbf{x}^{s},\mathbf{x}^{t})$ most, with a high counterfactual loss. A
faithful mask may contain some but not all salient features, thus can preserve
the SN prediction $f(\mathbf{x}^{s},\mathbf{x}^{t})$ while missing some
redundant salient features with a low counterfactual loss.

  * •

Conformity measures how much a local explanation overlaps the global salient
features. Fig. 2 shows that an additional minor feature or edge can be
selected beyond the global invariant explanations to accommodate local query-
reference pairs. Conforming to an invariant leads to more robustness against
variations in the reference $\mathbf{x}^{t}$.

##  III Self-learn to explain robustly

We propose optimization problems and algorithms to generate explanations
robustly without supervision.

###  III-A A general optimization formulation

The variables to be optimized are the two masks
$\mathbf{m}^{s}\in[0,1]^{p_{s}}$ and $\mathbf{m}^{t}\in[0,1]^{p_{t}}$ over
query $\mathbf{x}^{s}$ and reference $\mathbf{x}^{t}$, respectively333The
sigmoid function is a monotonic bijective function with the range $[0,1]$, we
let the masks be the output of the sigmoid function. . To balance the
faithfulness and simplicity, we have the objective:

$\displaystyle\min_{\mathbf{m}^{s},\mathbf{m}^{t}}\ell\left(f(\mathbf{x}^{s},\mathbf{x}^{t}),f(\mathbf{m}^{s}\otimes\mathbf{x}^{s},\mathbf{m}^{t}\otimes\mathbf{x}^{t})\right)$
(3) $\displaystyle+\gamma(\|a(\mathbf{m}^{s})\|+\|a(\mathbf{m}^{t})\|),$

where $\gamma$ is a hyperparameter to fine-tune the relative importance of the
two goals. $\ell(\cdot,\cdot)$ as defined by Eq. (1) promotes faithfulness and
$\|\cdot\|$ is the $\ell_{1}$-norm that promotes simplicity. Note that
simplicity can be structural (such as joint sparsity [41, 13]) and the
auxiliary function $a(\mathbf{m})$ maps from an unstructured mask to another
vector, upon which structural sparsity constraints can be imposed on the
tabular data (Section III-B) and graph data (Section III-C).

Stage 1. Saliency maps may lack robustness and we use a global invariant to
regulate $\mathbf{m}^{s}$ for more robustness against varying
$\mathbf{x}^{t}$. If there is domain knowledge regarding which features/edges
in a query $\mathbf{x}$ are salient, we can set the binary values in the
global mask $\mathbf{M}\in[0,1]^{p}$ for $\mathbf{x}$ accordingly. There is no
such knowledge in a more general case, and we propose to extract $\mathbf{M}$
as an invariant to encode global salient elements in $\mathbf{x}$, regardless
of references, using self-supervision learning (SSL). SSL [49, 19] train a
predictive model $h$ by contrasting $\mathbf{x}$ and its transformation
$T(\mathbf{x})$, where $\mathbf{x}$ can be a graph [49, 19] or an image [4].
The objective function in SSL is:

$h^{\ast}=\min_{h}\mathcal{L}_{self}(T,\mathbf{x},h)=\min_{h}\ell(h(\mathbf{x}),h(T(\mathbf{x}))),$

where $T(\cdot)$ is a given transformation. For example, $T(\cdot)$ can be
cropping and rotating of images [4]. The most relevant transformation to our
work is to use random walk to mask out irrelevant parts of a graph [19], and
$T(\mathbf{x})=\mathbf{M}\otimes\mathbf{x}$. SSL uses a fixed $T$ function to
learn $h$, while we are interested in learning a $T$, which is a global mask
for $\mathbf{x}$ regardless of different references compared using a fixed SN
model $f$. We formulate the following optimization problem:

$\displaystyle\min_{\mathbf{M}}$
$\displaystyle\ell\left(f(\mathbf{x},\mathbf{x}),f(\mathbf{x},\mathbf{M}\otimes\mathbf{x})\right)+\gamma\|a(\mathbf{M})\|,$
(4) $\displaystyle\textnormal{s.t.}\quad g_{i}(\mathbf{M})\leq 0,i=1,\dots,c.$
(5)

$\mathbf{M}$ is expected to extract the salient features of $\mathbf{x}$ to
maximally preserve information in $\mathbf{x}$, indicated by a low
faithfulness loss (Eq. (1)) when comparing $\mathbf{x}$ and
$\mathbf{M}\otimes\mathbf{x}$. The constraint functions $g_{i}(\mathbf{M})$
will be specified for tabular and graph data in the following two sections.
Unsupervised feature selection [47] learns important features without
considering the SN architecture and has inferior performance in the
experiments.

Stage 2. After finding $\mathbf{M}^{s}$ and $\mathbf{M}^{t}$ for
$\mathbf{x}^{s}$ and $\mathbf{x}^{t}$, respectively, using Eqs. (4)-(5), we
fix the global masks $\mathbf{M}^{s}$ and $\mathbf{M}^{t}$ and incorporate
them as constraints in the following optimization problem to find local masks
$\mathbf{m}^{s}$ and $\mathbf{m}^{t}$:

$\displaystyle\min_{\mathbf{m}^{s},\mathbf{m}^{t}}\ell\left(f(\mathbf{x}^{s},\mathbf{x}^{t}),f(\mathbf{m}^{s}\otimes\mathbf{x}^{s},\mathbf{m}^{t}\otimes\mathbf{x}^{t})\right)$
(6)
$\displaystyle+\gamma\left(\|a(\mathbf{m}^{s})\|+\|a(\mathbf{m}^{t})\|\right)$
s.t. $\displaystyle\quad
g_{i}(\mathbf{m})=a(\mathbf{m}^{s})_{i}-a(\mathbf{M}^{s})_{i}\leq
0,\>i=1,\dots,c_{s},$ (7) $\displaystyle\quad
g_{c_{s}+i}(\mathbf{m})=a(\mathbf{m}^{t})_{i}-a(\mathbf{M}^{t})_{i}\leq
0,\>i=1,\dots,c_{t}.$ (8)

$a(\cdot)_{i}$ means the $i$-th element of $a(\cdot)$, and $c_{s}$ and $c_{t}$
are the number of the constraints derived from the auxiliary function due to
structural sparsity. Notice that $a(\cdot)$ is monotonic, so that structural
sparsity in the global mask $\mathbf{M}$ enforces structural sparsity in the
local masks $\mathbf{m}$.

###  III-B Optimization problem for tabular data

Stage 1. Without a particular reference $\mathbf{x}^{t}$, a global mask over a
query can at best identify salient major features, such as Age, in
$\mathbf{z}^{s}$. We use the auxiliary function to find a global invariant
mask $\mathbf{N}\in[0,1]^{q}$ over the major features, where
$\mathbf{N}_{i}=a(\mathbf{M})_{i}=1-\prod_{j}(1-\mathbf{M}_{i,j})$ is the
importance of the $i$-th major feature444We tried alternatives, such as
$\mathbf{N}_{i}=\sum_{k}\mathbf{M}_{i,k}$ and
$\mathbf{N}_{i}=\prod_{k}\mathbf{M}_{i,k}$. They cannot focus on minor
features for a significant major feature, or lead to numerical underflow
issues., and $\mathbf{M}_{i,j}$ indicates the global importance of the $j$-th
value of the $i$-th major categorical feature of the query $\mathbf{x}$. As we
already encode the dependencies among minor features in $a(\mathbf{M})$, there
is no more constraints in Eq. (5) ($c=0$).

Stage 2. Comparing with $\mathbf{x}^{t}$, we further identify salient minor
features, such “Age<25”, associated with the salient major features. For
tabular data, any two input vectors to SN are aligned, so we optimize a single
mask $\mathbf{m}=\mathbf{m}^{s}=\mathbf{m}^{t}$ to find salient features for
both instances. We use the same auxiliary function for the local masks
$\mathbf{n}=a(\mathbf{m})$ such that
$\mathbf{n}_{i}=1-\prod_{j}(1-\mathbf{m}_{i,j})$ in Eq. (6). As we focus on
finding masks for the query $\mathbf{x}^{s}$ with varying references
$\mathbf{x}^{t}$, only Eq. (7) is kept ($c_{s}=q$, the number of major
features). Alternatively, we formulate an unconstrained optimization problem:

$\min_{\mathbf{m}}\ell\left(f(\mathbf{x}^{s},\mathbf{x}^{t}),f(\mathbf{m}\otimes\mathbf{x}^{s},\mathbf{m}\otimes\mathbf{x}^{t})\right)+\gamma\|\mathbf{n}\|+\beta\textnormal{KL}(\mathbf{n}\|\mathbf{N}),$
(9)

where
$\textnormal{KL}(\mathbf{n}\|\mathbf{N})=\sum_{i=1}^{q}\textnormal{KL}(\mathbf{n}_{i}\|\mathbf{N}_{i})$
and $\textnormal{KL}(\mathbf{n}_{i}\|\mathbf{N}_{i})$ is the KL-divergence
between $\mathbf{n}_{i}$ and $\mathbf{N}_{i}$, treated as the means of two
binary random variables. According to [2] (Section 10.1), the KL-
regularization encourages $\mathbf{n}_{i}$ to be smaller than
$\mathbf{N}_{i}$.

###  III-C Optimization problems for graphs

We set $a(\mathbf{M})=\mathbf{M}$ for masks on graphs. Isolated single-edged
subgraphs are not only difficult for domain experts to interpret, but can also
disturb the working of the GNN within the SN. Therefore, the selection of two
adjacent edges should be related. We consider such dependencies in stage 1,
where the constraints in Eq. (5) encourage the connectivities,

$\displaystyle
g_{jk}(\mathbf{M})=\|\mathbf{M}_{j}-\mathbf{M}_{k}\|-\epsilon\leq
0,j,k\textnormal{ adjacent in }G,$ (10)

where $\mathbf{M}_{j}\in[0,1]$ is the mask for the $j$-th edge. The
constraints indicate that the selection of the $j$-th edge can lead to the
selection of the $k$-th edge if they share a node [29], and $\epsilon$
controls the co-occurrence of the two edges. After obtaining $\mathbf{M}^{s}$
and $\mathbf{M}^{t}$ for each graph, the local masks $\mathbf{m}^{s}$ and
$\mathbf{m}^{t}$ over $\mathbf{G}^{s}$ and $\mathbf{G}^{t}$ are optimized by
solving problem Eqs. (6)-(8), using $\mathbf{M}^{s}$ and $\mathbf{M}^{t}$ as
constants in the constraints. In general, $\mathbf{G}^{s}$ and
$\mathbf{G}^{t}$ have different numbers of nodes, thus $\mathbf{m}^{s}$ and
$\mathbf{m}^{t}$ can lead to different numbers of constraints ($c_{s}=p^{s}$
and $c_{t}=p^{t}$). Similar to Eq. (9), one can use KL-regularization terms to
enforce the constraints.

###  III-D Optimization algorithm and convergence

If we adopt the KL-regularization to incorporate global invariance as in Eq.
(9) (referred to as SNX-KL), SGD can be used and the global masks act as
regularization rather than hard constraints. Since the objectives are not
convex due to SN architecture, only convergence to local optima can be
characterized, as in non-convex optimization [31].

Alternatively, global explanations on graph data (Eq. (4)-(5)) and local
explanations on both tabular and graph data (Eq. (6)-(8)) can be found by
solving constrained optimization problems. We adopt the gradient descent-
ascent (GDA) algorithm [25] to allow violations of the constraints. Take
optimizing local masks as an example, the mask to optimize is
$\mathbf{m}=\mathbf{m}^{s}=\mathbf{m}^{t}$ for tabular data and
$\mathbf{m}=[\mathbf{m}^{s};\mathbf{m^{t}}]$ (the concatenation of
$\mathbf{m}^{s}$ and $\mathbf{m^{t}}$) for graph data. The objective function
$g_{0}(\mathbf{m})$ is that in Eq. (4) or Eq. (6), and the inequality
constraints $g_{i}(\mathbf{m}),\forall i\in\\{1,\dots,c\\}$ are those defined
in or Eq. (5) or Eqs. (7)-(8), with $c$ being the total number of inequality
constraints in each problem. In Eqs. (7) - (8), $c=q$ in tabular data, and
$c=p^{s}+p^{t}$ in graph data. We introduce the non-negative Lagrange
multipliers $\boldsymbol{\lambda}\in\mathbb{R}_{+}^{c}$ and construct the
Lagrangian

$\mathcal{L}(\mathbf{m},\boldsymbol{\lambda})=g_{0}(\mathbf{m})+\sum_{i=1}^{c}\lambda_{i}g_{i}(\mathbf{m}),$
(11)

Then gradient descent is applied to $\mathbf{m}$ and gradient ascent is
applied to $\boldsymbol{\lambda}$ with learning rates $\eta_{1}$ and
$\eta_{2}$:

$\mathbf{m}\leftarrow\mathbf{m}-\eta_{1}\frac{\partial\mathcal{L}}{\partial\mathbf{m}},\hskip
14.45377pt\boldsymbol{\lambda}\leftarrow\boldsymbol{\lambda}+\eta_{2}\frac{\partial\mathcal{L}}{\partial\mathbf{\boldsymbol{\lambda}}}.$
(12)

Between the two updates, we use the latest $\mathbf{m}$ to evaluate the
partial derivatives with respect to $\boldsymbol{\lambda}$. Also, the
$\boldsymbol{\lambda}$ vector is normalized to have length one before entering
the next update iteration. The GDA-based SN explanation (SNX) algorithm is
given in Algorithm 1. The time complexity of each optimization iteration is
the sum of that of training the SN using back-propagation and that of
evaluating the $c$ constraints.

Algorithm 1 SNX: Siamese Network Explanation with GDA

1: Input: a target SN model $f$, a query instance $\mathbf{x}^{s}$ and
reference instance $\mathbf{x}^{t}$, optional human-defined constraints in
$\mathbf{M}^{s}$ and $\mathbf{M}^{t}$, learning rate $\eta_{1},\eta_{2}$ for
$\mathbf{m}$ and $\boldsymbol{\lambda}$.

2: Output: local masks $\mathbf{m}^{s}$ for $\mathbf{x}^{s}$, and
$\mathbf{m}^{t}$ for $\mathbf{x}^{t}$.

3: Init: $\boldsymbol{\lambda}=[1/c,\dots,1/c]\in\mathbb{R}^{c}$.

4: if $\mathbf{M}^{s}$ and $\mathbf{M}^{t}$ not given then

5: Extract global masks $\mathbf{M}^{s}$ and $\mathbf{M}^{t}$ by Eqs. (4)-(5)
$\rhd$SSL

6: end if

7: Pretrain $\mathbf{m}^{s},\mathbf{m}^{t}$ without constraints using Eq. (6).

8: Solve the full constrained optimization problems Eqs. (6)-(8) using GDA to
find local masks $\mathbf{m}^{s}$ and $\mathbf{m}^{t}$.

Convergence. The Lagrangian is nonconvex-concave, in fact, linear in the dual
variables. The GDA algorithm is convergent based on Theorem 4.4 of the work
[25], given the Lagrangian satisfies their Assumption 4.2, reproduced below:

  1. 1.

$\mathcal{L}$ is $l$-smooth and $\mathcal{L}(\cdot,\boldsymbol{\lambda})$ is
$L$-Lipschitz for each $\boldsymbol{\lambda}$ and
$\mathcal{L}(\mathbf{m},\cdot)$ is concave for each $\mathbf{m}$.

  2. 2.

The domain of $\boldsymbol{\lambda}$ is convex and bounded.

We verify these assumptions: if the target SN is a composition of smooth
function (excluding functions such as ReLU), then $\mathcal{L}$ is smooth in
both the primal variable $\mathbf{m}$ and the dual variable
$\boldsymbol{\lambda}$; since the masks are all non-negative, the $\ell 1$
penalties turn out to be just the sum of the elements in the masks. Due to the
smoothness, $\mathcal{L}(\cdot,\boldsymbol{\lambda})$ is $L$-Lipschitz.
$\mathcal{L}$ is linear and thus concave in $\boldsymbol{\lambda}$. In
Algorithm 1, we normalize $\boldsymbol{\lambda}$ to the unit ball and thus the
second assumption is satisfied.

##  IV Experiments

TABLE II:  Performance of local masks. The best methods except Pick-all on
each dataset is boldfaced, and the runner-up is highlighted by $\ast$. $\circ$
indicates significantly better performance according to $t$-tests. Column
Pick-all provides lower (underlined) and upper bounds (overlined) of
faithfulness (the counterfactual (CF) of selecting all features is equivalent
to the faithfulness (FA) of selecting no feature)).  (a) Performance (mean
with std. in parenthesis) of each algorithm in terms of faithfulness. Lower is
better ($\downarrow$).

Method | Pick-all | DES | SNX-global | SM | SNX-UC | SNX-KL | SNX-DES | SNX-inter | SNX-union | SNX
---|---|---|---|---|---|---|---|---|---|---
Adult |  0.65 (0.14) | 1.67 (2.46) | 0.71 (0.18) | 0.81 (0.72) |  0.68 (0.14) $\ast$ | 0.69 (0.20) |  0.66 (0.14) |  0.66 (0.14) |  0.66 (0.14) |  0.66 (0.14) $\circ$
Bank |  0.62 (0.16) | 0.82 (0.85) | 0.72 (0.22) | 0.71 (0.24) |  0.65 (0.16) $\ast$ | 0.66 (0.16) |  0.63 (0.16) |  0.63 (0.16) |  0.63 (0.16) |  0.63 (0.16) $\circ$
Credit |  0.64 (0.15) | 1.15 (1.73) | 0.70 (0.19) | 1.13 (1.35) | 0.72 (0.19) | 0.74 (0.21) |  0.69 (0.18) $\ast$ |  0.68 (0.16) |  0.68 (0.16) |  0.68 (0.16) $\circ$
COMPAS |  0.62 (0.19) | 0.76 (0.57) | 0.71 (0.65) | 0.79 (0.73) | 0.64 (0.17) |  0.63 (0.19) $\ast$ |  0.62 (0.19) |  0.62 (0.19) |  0.62 (0.19) |  0.62 (0.19) $\circ$

(b) Performance (mean with std. in parenthesis) of each algorithm in terms of
counterfactual. Higher is better. ($\uparrow$)

Method | Pick-all | DES | SNX-global | SM | SNX-UC | SNX-KL | SNX-DES | SNX-inter | SNX-union | SNX
---|---|---|---|---|---|---|---|---|---|---
Adult |  $\overline{7.50}$ (2.05) | 0.85 (0.49) | 0.78 (0.14) | 1.02 (1.09) |  1.28 (1.57) $\ast$ | 0.99 (0.92) |  1.31 (1.62) $\circ$ | 1.25 (1.53) | 1.26 (1.54) | 1.26 (1.54)
Bank |  $\overline{6.86}$ (2.49) | 1.26 (1.58) | 0.71 (0.11) | 1.67 (2.09) | 1.80 (2.25) | 1.25 (1.47) | 2.54 (2.83) |  2.78 (2.97) $\ast$ |  2.78 (2.97) $\ast$ |  2.79 (2.97) $\circ$
Credit |  $\overline{7.54}$ (2.26) | 0.74 (0.23) | 0.83 (0.19) |  1.23 (0.82) $\ast$ |  1.24 (1.17) $\circ$ | 0.89 (0.57) | 1.16 (1.10) | 0.97 (0.90) | 0.97 (0.90) | 0.97 (0.88)
COMPAS |  $\overline{7.02}$ (2.52) | 1.86 (2.53) | 0.72 (0.09) | 1.76 (2.07) | 3.65 (3.22) | 2.65 (2.74) | 4.56 (3.48) | 4.93 (3.43) |  5.00 (3.43) $\circ$ |  4.98 (3.43) $\ast$

TABLE III:  Performance of global invariant masks in faithfulness (FA) and counterfactual loss (CF), reported in mean with std. in parenthesis. The best methods except Pick-all are boldfaced. The underlines for FA and overlines for CF in the column “Pick-all” indicate the lower and upper bounds of FA (the CF of selecting all features is equivalent to the FA of selecting no feature). Sensitivity study w.r.t. different numbers of selected features is given in Fig. 7.  Metrics | Datasets | Pick-all | DES | SNX-global
---|---|---|---|---
FA ($\downarrow$) | Adult |  0.00 (0.00) | 0.28 (0.28) |  0.00 (0.00)
Bank |  0.00 (0.00) | 0.21 (0.22) |  0.00 (0.00)
Credit |  0.00 (0.00) | 0.31 (0.36) |  0.00 (0.00)
COMPAS |  0.00 (0.00) | 0.11 (0.19) |  0.00 (0.00)
Molecule |  0.08 (0.00) | - |  0.91 (1.01)
BP |  0.01 (0.00) | - |  0.00 (0.00)
CF ($\uparrow$) | Adult |  $\overline{0.69}$ (0.21) | 0.33 (0.21) |  0.69 (0.21)
Bank |  $\overline{0.62}$ (0.26) | 0.34 (0.19) |  0.62 (0.26)
Credit |  $\overline{0.62}$ (0.21) | 0.31 (0.26) |  0.63 (0.21)
COMPAS |  $\overline{0.56}$ (0.18) |  0.56 (0.21) |  0.56 (0.18)
Molecule |  $\overline{6.80}$ (0.01) | - |  6.61 (0.49)
BP |  $\overline{1.11}$ (1.39) | - |  1.22 (1.54)

###  IV-A Experimental settings

Datasets. We conduct experiments on four tabular datasets [33, 34] and two
graph datasets (molecules [35] and brain networks [30]). We split the
instances into training ($70\%$) and test ($30\%$) sets, and Section IV-H
provides details about pairs generation. The target SN is trained on the
training portion and then held fixed during explanation generation on the test
portion.

Metrics. We evaluate the faithfulness (FA) by Eq. (1), counterfactual loss
(CF) by Eq. (2), and conformity of the explanations with the same percentage
of selected salient features or edges. We also study the sensitivity of these
metrics w.r.t. a different number of selected features/edges (simplicity). The
conformity is evaluated by averaging the Jaccard similarity between global and
local masks, $J=\frac{|a(\textbf{M})\cap a(\textbf{m})|}{|a(\textbf{M})\cup
a(\textbf{m})|}$, between $\mathbf{M}^{s}$ and $\mathbf{m}^{s}$, and between
$\mathbf{M}^{t}$ and $\mathbf{m}^{t}$, respectively.

Baselines and variants. There are several options to obtain local masks
$\mathbf{m}^{s}$ for the queries. The following three methods use global masks
as local masks and are agnostic to references.

  * •

Pick-all: set all elements in the global masks to one.

  * •

DES (tabular data only): an unsupervised feature selection [47] that generates
pseudo labels for all pairs of instances using kNN to supervise the learning
of a feature selector. The selected features of the query are used when
comparing with different references.

  * •

SNX-global: solve Eq. (4) for $\mathbf{M}^{s}$ which is treated as a local
mask without stage 2 local mask optimization.

The following baselines disregard constraints by global masks.

  * •

Saliency maps (SM) [1]: take the gradient of $\ell^{\textnormal{SN}}$ with
respect to the input $\mathbf{x}^{s}$ and retain the features with the largest
gradient magnitudes.

  * •

SNX-unconstrained (SNX-UC): minimize the objective Eq. (6) without the
constraints Eqs. (7)-(8).

  * •

GNNExplainer (GNNExp) [48]: learn soft masks for edges by maximizing the
mutual information (MI) between the model’s predictions w.r.t. original and
masked graphs, and use the entropy as part of regularization to encourage the
sparsity and simplicity of masks. Applying GNNExp [48] to SN is similar to
SNX-UC, but with different objective functions and regularization terms in Eq.
(6).

  * •

PGExplainer (PGExp) [29]: train a shareable generator for all graphs by
maximizing the MI between the SN predictions on the original and masked
graphs. The generator generates edge masks for each graph to be explained.

The following three baselines extract local masks with variants of global
masks. They apply to tabular data only the features are aligned in the query
and the reference.

  * •

SNX-DES: optimize $\mathbf{m}$ by Eqs. (6)-(8), with global mask
$\mathbf{M}^{s}$ found by DES used in the constraints Eqs. (7)-(8).

  * •

SNX-inter: a variant of SNX. Instead of using $\mathbf{M}^{s}$ to constrain
$\mathbf{m}^{s}$, this baseline uses the element-wise minimum
$\mathbf{M}=\min(\mathbf{M}^{s},\mathbf{M}^{t})$, analogous to intersecting
the two global masks over the query and the reference, leading to a more rigid
global mask constraint.

  * •

SNX-union: similar to SNX-inter but use the element-wise maximum
$\mathbf{M}=\max(\mathbf{M}^{s},\mathbf{M}^{t})$ to simulate the union of
$\mathbf{M}^{s}$ and $\mathbf{M}^{t}$, leading to a less rigid constraint.

###  IV-B Quantitative evaluation on tabular datasets

Evaluations of global masks. We use
$\ell(f(\mathbf{x},\mathbf{x}),f(\mathbf{x},\mathbf{M}\otimes\mathbf{x}))$ as
faithfulness and
$\ell(f(\mathbf{x},\mathbf{x}),f(\mathbf{x},(1-\mathbf{M})\otimes\mathbf{x}))$
as CF loss to evaluate global masks. By default, we select the top 10 most
important minor features into the global masks. In Table III, with all
features selected, the baseline Pick-all does not generate meaningful
explanations but provides the best performance in FA and CF, respectively
(indicated by the under- and over-lines). SNX-global outperforms DES and
achieves the same performance as Pick-all. Since all samples in the four
tabular datasets have less than 10 major features, when SNX-global can pick 10
minor features, self-supervised learning (Eq. (4)) can consider the target SN
and select the active locations in the one-hot vectors of each instance.

Evaluations of local masks. In Table II(b), we compare the faithfulness and
counterfactual losses of local masks found by various methods. We answer the
following questions.

Does the two-stage optimization find better local masks? Overall, the best-
performing methods in local mask faithfulness are in the last four columns
representing variants of the SNX using GDA, with different global masks as
constraints. In terms of counterfactual loss, the optimal local masks
outperform the remaining methods, except on the Credit dataset (SNX-UC has no
constraint and can include more salient features).

Which variants of global masks help SNX? We further compare the last four
columns of Table II(b) and find similar faithfulness losses. However, there is
no clear winner in terms of counterfactual loss. Since we aim to interpret a
local reference-specific explanation along with the associated global
invariant mask as a context, SNX and its variants are preferred over DES,
based on Table III.

Why do the other methods underperform SNX and its variants?

  * •

DES does not perform well and has the worst faithfulness except on COMPAS,
where SM is the worst. That is because DES is agnostic about the SN
architecture and does not consider the reference instance when finding
$\mathbf{M}^{s}$ to mask both $\mathbf{x}^{s}$ and $\mathbf{x}^{t}$. DES is
also not performing well in the counterfactual loss, indicating that it fails
to include the most salient features. These drawbacks can be addressed by the
stage 2 optimization where the SN model is put back (SNX-DES is among of the
best performers, noting that the global masks found by DES are only soft
constraints).

  * •

SNX-global uses $\mathbf{M}^{s}$ found by the self-supervised mask learning
and takes the target SN into account. As a result, it has good performance in
faithfulness. However, it is worse than DES in the counterfactual loss on 3
out of 4 datasets, meaning that it can miss even more salient features.

  * •

SM takes the reference into account and outperforms DES in both metrics except
on COMPAS. Interestingly, on the Credit dataset, this method outperforms those
methods in the last four columns in the counterfactual loss, indicating that
gradients can locate the most salient features.

  * •

SNX-UC: without constraints from the global masks, it performs stage 2
optimization to find local masks. Therefore, it is a strong baseline: it is
the runner-up in faithfulness on Adult and Bank and is the best in
counterfactual loss on Credit. However, no constraint leads to less conformity
to global invariant masks (Fig. 3 and Table IV).

  * •

SNX-KL is very similar to SNX-UC, except that the soft constraints are
implemented as KL-divergence penalty terms. They have similar faithfulness
performance, but SNX-KL significantly underperforms SNX-UC in counterfactual
loss, indicating that the constraints are actually working by selecting just
enough salient features but possibly excluding redundant salient ones.

Figure 3:  Jaccard similarity measuring conformity of multiple local masks to
a global invariant mask.

How the local masks conform to the global invariant masks? In Fig. 3, we
report the average of Jaccard similarities between the important major
features selected by global masks $\textbf{N}^{s}$ and local masks
$\textbf{n}^{s}$, when comparing $\mathbf{x}^{s}$ to multiple
$\mathbf{x}^{t}$. The higher similarity indicates the more conformity of local
masks to global masks. Moreover, high conformity indicates that local masks of
a query w.r.t. different references are regulated by global invariant masks,
and these local masks are more robust, since they highlight different features
adaptively within the selected global invariant features, when comparing with
various references. As shown in Fig. 3, except for the COMPAS dataset, SNX
with GDA results in the best conformity (highest similarity), regardless of
the global invariant masks used. SNX is the runner-up on COMPAS next to SNX-
UC. The low CF of SNX-global in Table II(b) can be blamed. SNX-global can find
some important features but miss some as well. SNX bypass global constraints
and find other important features missed by SNX-global for better FA. In
Section IV-E, we further study the conformity.

###  IV-C Quantitative evaluation on graph datasets

Figure 4: Faithfulness (FA), counterfactual (CF), and conformity (in Jaccard
similarity) of local masks on graph datasets.

For graph data, we select the top 75% important edges by default. In Table
III, we evaluate the average faithfulness and counterfactual loss of the
global masks over all test graphs. SNX-global works well on graph data, with
mean faithfulness much closer to the lower bound than the upper bound
(represented by FA and CF in the Pick-all column).

In Fig. 4, we compare local graph masks with respect to faithfulness,
counterfactual loss, and conformity. On the molecule dataset, SNX-KL can
achieve the best (the lowest) faithfulness and highest conformity ($\sim$90%)
to global masks found by SNX-global (which always has conformity 1). SNX with
GDA and SNX-UC have the best CF loss, while SNX achieves better (lower) FA
than SNX-UC. Both GNNExp and PGExp are competitive baselines, whose
counterfactual is similar to SNX-KL’s but are significantly worse in the other
two metrics. Four methods, SM, GNNExp, PGExp, and SNX-UC, disregard any
constraints and have worse conformity (overlapping only about 60% of global
masks’ edges) and worse faithfulness than SNX-KL.

On the BP dataset where graphs are much larger, both SNX-KL and SNX achieve
better FA and conformity, and thus more robust than other methods. Since SNX-
global has already provided very competitive global masks w.r.t. FA and CF,
SNX-KL can result in a similarly good performance when following SNX-global a
lot, while SNX sacrifices a bit of conformity to bypass some global
constraints for better masks w.r.t. FA and CF. On the contrary, SM has the
worst conformity (<50%) with only a slightly better faithfulness than SNX-KL,
and it validates the analysis in Section II-C that SM has worse robustness as
it is too sensitive to different references given a query. PGExp performs
poorly on all three metrics, while GNNExp is much better (but still worse than
SNX-KL and SNX in all three metrics). The reason can be that all pairs of
graphs share the same generator in PGExp while SNX-based methods and GNNExp
optimize masks for each specific pair of graphs. Compared with molecule
dataset, graphs in BP are much larger and it is harder to find shared
parameters that work for all pairs of graphs.

###  IV-D Convergence of GDA

Figure 5: $\ell 2$ norms of the gradients of Lagrangian w.r.t. $\mathbf{m}$’s
and $\boldsymbol{\lambda}$’s when running GDA on the Adult and Molecule
datasets. Line indicates the mean and the colored region for variance.

To track the convergences of GDA, Fig. 5 records the norm of the gradients of
the Lagrangian w.r.t. the primal and dual variables. Both norms go close to 0
in 100 iterations, confirming the convergence of GDA. Similar trends are found
in other datasets (not shown due to space limit).

###  IV-E More on conformity

Figure 6: The ratio of instances violates constraints in the first 200
(tabular data) and 400 iterations (graph data) by SNX-KL and SNX.

Fig. 6 compares the violation of constraints by SNX and SNX-KL during
optimization for all six datasets. We evaluate Eqs. (7)-(8) using the masks
without selecting top edges. To make both methods comparable, we set the same
hyper-parameters as illustrated in Section IV-H using no pre-train to ensure
that SNX-KL and SNX start with the same initialization. SNX breaks fewer
constraints in four tabular datasets and BP. Notice that SNX-KL keeps
violating about 30% of constraints after about 70 iterations. We conjecture
that SNX-KL converges to a “minimizer” balancing both the objective functions
and soft constraints. SNX-KL has higher violations in Fig. 6 but better
conformity in Fig. 4. since the top 75% edges are selected from the masks to
generate Fig. 4, and masks are evaluated directly in Fig. 6. The decoding may
select one edge but drop the other even if their importance are the same.

###  IV-F Sensitivity analysis

Figure 7: Sensitivity of global (left) and local (right) masks w.r.t.
faithfulness (FA) and counterfactual (CF).

In Fig. 7, we plot the quality of the global masks (left column) and local
masks (right column) on a tabular dataset (top row) and a graph dataset
(bottom row). Regarding global masks, on the Adult dataset, SNX-global
outperforms DES and remains good even when smaller than 10 minor features are
selected. On the Molecule dataset, a higher percentage of edges need to be
selected to preserve the connection patterns that are critical to GNN.
Regarding local masks, a much smaller number of minor features are needed to
achieve good faithfulness (red curves for FA go down more rapidly), though
more are needed to cover all salient minor features (green curves for CF going
up more slowly). On the graph dataset, the stage 2 optimization can locate a
smaller percentage of edges to preserve SN predictions, and a higher
percentage of edges are needed to include all important edges, as seen in the
CF losses. Similar trends are found in other datasets. Comparing FA of the
global and the local masks in Adult, we found that the global mask selects
more features (9) than local one (about 5) to reach the elbow point. The
reason is that global mask needs to figure out all non-zero features but local
one only picks the non-zero features indicating the (dis)similarity of two
feature vectors. Similar results can be found in Molecule.

###  IV-G Qualitative evaluation

TABLE IV: Visualization of local masks extracted by SM, SNX-UC, and SNX when comparing a query with two different references.  Adult |  Work |  Race |  Edu. |  Age |  Hrs/Wk |  Marriage |  Occup. |  Relation |  Sex |  Label
---|---|---|---|---|---|---|---|---|---|---
Ref. 1 | SM |  |  |  |  |  |  |  |  |  | 0
SNX-UC |  |  |  |  |  |  |  |  |  | 0
SNX |  |  |  |  |  |  |  |  |  | 0
Query | SNX-global |  |  |  |  |  |  |  |  |  | 0
Ref. 2 | SNX |  |  |  |  |  |  |  |  |  | 1
SNX-UC |  |  |  |  |  |  |  |  |  | 1
SM |  |  |  |  |  |  |  |  |  | 1

Adult Dataset. Table IV shows a case study from the Adult dataset. The global
invariant mask $\mathbf{N}^{s}$ over major features $\mathbf{z}^{s}$ (Query)
is highlighted in blue. Similarly, local masks $\mathbf{n}$ over major feature
vectors extracted by SM, SNX-UC, and SNX when comparing query with Ref.1 and
Ref.2 are colored red. Higher color saturation indicates more saliency. It is
clear that SNX closely follows the constraints set by the global mask
$\mathbf{N}^{s}$: SNX always places the same or lower importance on a feature
than that place by SNX-global. On the contrary, SNX-UC and SM do not consider
constraints and both highlight some features, such as Race and Age, that are
not considered important by SNX-global. When fairness is a concern, not
selecting sensitive features such as Race, Age, and Sex can be a constraint
built in the global mask $\mathbf{N}^{s}$. Without such domain requirements as
labeled data, it is encouraging to see the self-supervised learning can avoid
selecting these sensitive features. We note that whether the query is compared
with references in the same or different classes, SNX conforms to the global
invariant.

Figure 8: Explaining brain network matching in the BP dataset. The numbered
nodes and represent the brain ROIs. Blue highlights globally salient edges and
red highlights locally salient edges. Edge thickness indicates the importance
of edges in different masks. SNX-global found important edges linking ROIs
(first subfigure), and both SNX-KL and SNX found local masks conforming to the
global mask.

Figure 9: Case study for molecules. Each highlighted subgraph appears in two
promising molecules and never in the useless molecules.

Brain networks. Fig. 8 shows masks learned by SNX-global and four local
methods on the BP dataset, respectively. The numbered colored nodes are brain
regions of interest (ROIs) related to the human dorsal and ventral systems,
and edges connected to these nodes are colored accordingly. These ROIs, such
as ventromedial prefrontal cortex (#39), dorsolateral prefrontal cortex (#17),
superior parietal lobule (#10), and anterior cingulate cortex (#51), could be
highly affected by bipolar disorder according to neuroscience studies [3, 52].
As a result, SNX-global well captures many edges adjoined to these ROIs,
particularly the interconnections among the aforementioned four ROIs (#39,
#17, #10 and #51). Also, SNX and SNX-KL found local masks more conformal to
global mask than the baselines SNX-UC and SM.

Chemical molecules. We extract all the 38 pairs of connected cliques that
appear in the explaining subgraphs. After consulting with one of the authors
who is a chemical engineer, we found the salient pairs of cliques that appear
only in the positive or negative molecules. We display these fragments in Fig.
9, along with their frequencies in the entire dataset. For example,
heteroatoms (i.e., O and N atoms) that are a part of a ring are often found in
positive molecules. Further, interestingly, consecutive heteroatoms within
rings (NN and OO) were also found to be only in positive molecules. The
algorithm did identify fragments, such as “CC-C1COCN”, that appear only in the
negative class, but belong to motifs that might be considered favorable. We
posit that the reason for this is that the junction tree cannot accurately
specify how two cliques are connected (i.e., to which atom of the ring
"C1COCN1" is the fragment "CC" connected to), and that the dataset used to
train the GNN may not be sufficiently large and diverse due to its
construction [35].

###  IV-H Reproducibility checklist

Pairs generation. For all six datasets, in both training portion and test
portion, we pair each sample with other 4 randomly selected samples in the
same portion, where 2 are from the same class and the other 2 from the
different class. Hypreparameters settings. For all experiments,
$\eta_{1}=10^{-1},\eta_{2}=10^{-3}$ in Eq. (12) and $\beta=1$ in SNX-KL. On
the tabular datasets, $\gamma=10^{-3}$ in both Eq. (4) and Eq. (6). To extract
global masks, learning rate is $10^{-1}$, and $MaxIter=50$; as for local
masks, $PreIter=50,MaxIter=100$. On graph datasets, $\gamma$ in Eq. (4) and
Eq. (6) is $10^{-1}$ for Molecule and $10^{-4}$ for BP. To extract global
masks, learning rate is $10^{-1}$, and $MaxIter=200$; as for local masks,
$PreIter=0,MaxIter=400$.

##  V Related work

Explainability in machine learning can be attained by intrinsically
transparent models [23, 27] or simpler surrogate models [38]. Global
explanations in prior work mean “regardless of input data”, while we define
global explanations differently for SN, meaning “regardless of the reference
instance.” In [39], the authors use global consistency constraints to
regularize local explanations, with different definitions of “global
consistency” and target model architecture. Explainability have been
extensively studied for tabular data [38], images [40, 8], and texts [17], and
more recently, on graph data [48, 1, 29, 12, 50, 44, 24, 51].

Robustness in explanations is gaining attention [10, 22, 46]. In [10], the
goal is to train neural networks for image classification that has robust
explanations with malicious data manipulations. In [46], the vulnerability of
explanations of architecture with a single input image is analyzed. In the
prior work, explanation robustness is analyzed local to a neighborhood of the
single input $\mathbf{x}$, while we characterize robustness with respect to
varying references in SN.

Explaining why two instances are similar or different has been only sparsely
researched [12, 24, 36, 43]. [12] extracts the most contrastive parts of the
graphs to tell the similarity (or difference) among those in the same class
(or different classes). [24] extracts contrast subgraphs for discriminating
two different groups of brain networks. In [36], salient attributes are
introduced to explain image similarity. [43] proposes to compare the explained
example with a prototype in the embedding space of the SN and reconstruction
is needed, while we learn masks on the input directly.

The convergence of GDA has been extensively studied in optimization, game
theory, adversarial training, and security. The closest work to our work is
[45], where the authors used GDA to solve a constrained optimization problem
to find counterfactual explanations for a classifier. Rather, we apply the
algorithm to solve a novel problem for SN explanation.

##  VI Conclusions

We address the robustness issues in explaining Siamese networks due to
changing compared reference objects. We formulated the problem of global
invariance when explaining the results of comparing two objects, where the
invariance is self-learned from unlabeled data. The optimization is done using
SGD and GDA that are provably and empirically convergent to high-quality
solutions. Case studies on a tabular dataset and human brain networks
demonstrate the meaningfulness of the learned invariant and conformity when
explaining local comparisons.

## References

  * [1] Federico Baldassarre and Hossein Azizpour.  Explainability techniques for graph convolutional networks.  ICML workshop, 2019.
  * [2] Christopher M Bishop.  Pattern recognition and machine learning.  springer, 2006.
  * [3] Chi-Hua Chen, John Suckling, Belinda R Lennox, Cinly Ooi, and Ed T Bullmore.  A quantitative meta-analysis of fmri studies in bipolar disorder.  Bipolar disorders, 13(1):1–15, 2011.
  * [4] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A Simple Framework for Contrastive Learning of Visual Representations.  In ICML, 2020.
  * [5] Davide Chicco.  Siamese neural networks: An overview.  Artificial Neural Networks, pages 73–94, 2021.
  * [6] Sumit Chopra, Raia Hadsell, and Yann LeCun.  Learning a Similarity Metric Discriminatively, with Application to Face Verification.  In CVPR, 2005.
  * [7] S. Dey, A. Dutta, J. I. Toledo, S. Ghosh, J. Lladós, and U. Pal.  Signet: Convolutional siamese network for writer independent offline signature verification.  ArXiv, abs/1707.02131, 2017.
  * [8] Amit Dhurandhar, Pin-Yu Chen, Ronny Luss, Chun-Chen Tu, Paishun Ting, Karthikeyan Shanmugam, and Payel Das.  Explanations based on the missing: Towards contrastive explanations with pertinent negatives.  NeurIPS, 2018.
  * [9] Ann-Kathrin Dombrowski, Maximillian Alber, Christopher Anders, Marcel Ackermann, Klaus-Robert Müller, and Pan Kessel.  Explanations can be manipulated and geometry is to blame.  In NeurIPS, 2019.
  * [10] Ann-Kathrin Dombrowski, Christopher J. Anders, K. Müller, and P. Kessel.  Towards robust explanations for deep neural networks.  ArXiv, abs/2012.10425, 2020.
  * [11] David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aspuru-Guzik, and Ryan P Adams.  Convolutional Networks on Graphs for Learning Molecular Fingerprints.  In NeurIPS. 2015.
  * [12] Lukas Faber, Amin K Moghaddam, and Roger Wattenhofer.  Contrastive graph neural network explanation.  In ICML Workshop, 2020.
  * [13] Jerome Friedman, Trevor Hastie, and Robert Tibshirani.  Sparse inverse covariance estimation with the graphical lasso.  Biostatistics, 2008.
  * [14] Amirata Ghorbani, Abubakar Abid, and James Y Zou.  Interpretation of Neural Networks is Fragile.  In AAAI, 2017.
  * [15] Bryce Goodman and Seth Flaxman.  European union regulations on algorithmic decision-making and a “right to explanation”.  AI magazine, 38, 2017.
  * [16] Rory Mc Grath, Luca Costabello, Chan Le Van, Paul Sweeney, Farbod Kamiab, Zhao Shen, and Freddy Lecue.  Interpretable credit application predictions with counterfactual explanations.  NeurIPS workshop, 2018.
  * [17] Sarthak Jain and Byron C Wallace.  {A}ttention is not {E}xplanation.  In NAACL. Association for Computational Linguistics, 2019.
  * [18] Ashish Jaiswal, Ashwin Ramesh Babu, Mohammad Zaki Zadeh, Debapriya Banerjee, and Fillia Makedon.  A survey on contrastive self-supervised learning.  Technologies, 9(1), 2021.
  * [19] Wei Jin, Tyler Derr, Haochen Liu, Yiqi Wang, Suhang Wang, Zitao Liu, and Jiliang Tang.  Self-supervised learning on graphs: Deep insights and new direction.  arXiv preprint arXiv:2006.10141, 2020.
  * [20] Wengong Jin, Regina Barzilay, and Tommi Jaakkola.  Junction tree variational autoencoder for molecular graph generation.  ICML, 2018.
  * [21] Peter Kolesar and Janet L Showers.  A robust credit screening model using categorical data.  Management Science, 31(2):123–133, 1985.
  * [22] Himabindu Lakkaraju, Nino Arsov, and Osbert Bastani.  Robust and Stable Black Box Explanations.  In ICML, 2020.
  * [23] Himabindu Lakkaraju, Stephen H Bach, and Jure Leskovec.  Interpretable Decision Sets: A Joint Framework for Description and Prediction.  In SIGKDD, 2016.
  * [24] Tommaso Lanciano, F. Bonchi, and A. Gionis.  Explainable classification of brain networks via contrast subgraphs.  SIGKDD, 2020.
  * [25] Tianyi Lin, Chi Jin, and Michael Jordan.  On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems.  In ICML, 2020.
  * [26] Zachary C Lipton.  The Mythos of Model Interpretability.  Queue, 2018.
  * [27] Yin Lou, Rich Caruana, and Johannes Gehrke.  Intelligible Models for Classification and Regression.  In SIGKDD, 2012.
  * [28] Scott M Lundberg and Su-In Lee.  A unified approach to interpreting model predictions.  In NeurIPS, pages 4765–4774, 2017.
  * [29] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang.  Parameterized explainer for graph neural network.  NeurIPS, 33, 2020.
  * [30] Guixiang Ma, Nesreen K Ahmed, Theodore L Willke, Dipanjan Sengupta, Michael W Cole, Nicholas B Turk-Browne, and Philip S Yu.  Deep graph similarity learning for brain data analysis.  In CIKM, 2019.
  * [31] Tengyu Ma.  Why do local methods solve nonconvex problems?  ArXiv, abs/2103.13462, 2020.
  * [32] Grégoire Montavon, Sebastian Lapuschkin, Alexander Binder, Wojciech Samek, and Klaus-Robert Müller.  Explaining nonlinear classification decisions with deep taylor decomposition.  Pattern Recognition, 2017.
  * [33] Sérgio Moro, Paulo Cortez, and Paulo Rita.  A data-driven approach to predict the success of bank telemarketing.  Decision Support Systems, 62, 2014.
  * [34] Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan.  Explaining machine learning classifiers through diverse counterfactual explanations.  In FAT$\ast$, pages 607–617, 2020.
  * [35] Kristin Paragian, Bowen Li, Morgan Massino, and Srinivas Rangarajan.  A computational workflow to discover novel liquid organic hydrogen carriers and their dehydrogenation routes.  Molecular Systems Design & Engineering, 5(10):1658–1670, 2020\.
  * [36] Bryan A Plummer, Mariya I Vasileva, Vitali Petsiuk, Kate Saenko, and David Forsyth.  Why do these match? explaining the behavior of image similarity models.  ECCV, 2019.
  * [37] Marcus E Raichle.  The brain’s default mode network.  Annual review of neuroscience, 38:433–447, 2015.
  * [38] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin.  Why should i trust you? explaining the predictions of any classifier.  In KDD, 2016.
  * [39] C. Rudin and Y. Shaposhnik.  Globally-consistent rule-based summary-explanations for machine learning models: Application to credit-risk evaluation.  Human-Computer Interaction eJournal, 2019.
  * [40] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  In ICCV, 2017.
  * [41] Noah Simon, Jerome Friedman, Trevor Hastie, and Rob Tibshirani.  A sparse-group lasso.  JOURNAL OF COMPUTATIONAL AND GRAPHICAL STATISTICS, 2013.
  * [42] Berk Ustun, Alexander Spangher, and Yang Liu.  Actionable Recourse in Linear Classification.  In FAT$\ast$, 2019.
  * [43] Lev V Utkin, Maxim S Kovalev, and Ernest M Kasimov.  An explanation method for siamese neural networks.  arXiv:1911.07702, 2019.
  * [44] Minh N. Vu and M. Thai.  Pgm-explainer: Probabilistic graphical model explanations for graph neural networks.  NeurIPS, 2020.
  * [45] Sandra Wachter, Brent D Mittelstadt, and Christopher Russell.  Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR.  ArXiv, abs/1711.0, 2017.
  * [46] Zifan Wang, H Wang, Shakul Ramkumar, Matt Fredrikson, Piotr Mardziel, and A Datta.  Smoothed Geometry for Robust Attribution.  In NeurIPS, 2020.
  * [47] Xiaokai Wei, Sihong Xie, Bokai Cao, and S Yu Philip.  Rethinking unsupervised feature selection: From pseudo labels to pseudo must-links.  In ECML-PKDD, pages 272–287. Springer, 2017.
  * [48] Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec.  Gnnexplainer: Generating explanations for graph neural networks.  In NeurIPS, pages 9244–9255, 2019.
  * [49] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen.  Graph contrastive learning with augmentations.  NeurIPS, 2020.
  * [50] Hao Yuan, Jiliang Tang, Xia Hu, and S. Ji.  Xgnn: Towards model-level explanations of graph neural networks.  SIGKDD, 2020.
  * [51] Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji.  Explainability in graph neural networks: A taxonomic survey.  arXiv:2012.15445, 2020.
  * [52] Niccolò Zovetti, Maria Gloria Rossetti, Cinzia Perlini, Eleonora Maggioni, Pietro Bontempi, Marcella Bellani, and Paolo Brambilla.  Default mode network activity in bipolar disorder.  Epidemiology and Psychiatric Sciences, 29, 2020.