Prediction of surface atoms in molecule from its graph
The Quantum Theory of Atoms in Molecules (QTAIM) provides a fairly unambiguous answer. First, I would like demonstrate the concept of an Atomic Basin. A region of space belongs to a given atom if the steepest ascent path through the electron density terminates at that atom.  Consider a plane that contains the nuclei of the water molecule:



and the atomic basins could also be represented in 3D:



These atomic basins are the QTAIM definitions of ATOMS in MOLECULES. Note that there are gradient paths for each atom that extend to infinity, hence each atom could be considered an "external atom."  (This is a quite trivial case, of course.) 

Now consider formamide in this configuration:



The atomic basins of form amide look like:



You can see that the carbon atom is fairly "inaccessible" in the plane of the molecule, but it does have some extent "peeking" out of the plane of the molecule (here, the maroon-colored basin, sorry for change-up in color):

 

This is a completely general concept, and so can be extended to any scenario. Here is a molecular graph of thiol on a silver cluster (meant to mimic a surface) (note the bond paths unambiguously show which atoms are bonded to what, even for C-Ag, S-Ag, H-Ag interactions where these "cooked-up" rules of hybridized bonding and "valency" are totally out of their league):



Plotting the atomic basins is just an exercise:



The final answer: you can define "interior atoms" as QTAIM atomic basins that do not have steepest ascent trajectories starting at infinity that terminate at that atom, such as an interior silver atom in the above example. If you are conceptually separating a system into a substrate and an adsorbate, then you could say "exterior" atoms of the substrate include the ones that have bond paths connecting the two. 

I must caution that as two or more atoms approach each other, their atomic basins change their shape.  (Of course they do!)  And so one must consider the possibility that atomic basins of "exterior" atoms move out of the way and lead to exposure of what was, in isolation, an interior atom.

(PS:  the atomic basins of peripheral atoms actually extend to infinity.  Here, I have applied cutoffs so that one can actually plot the molecule in a finite region of space.]